2012/06/12 by Luke Mathieson, Mathieson, Luke · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Methods in Verification
paper · pdf · doi:10.48550/arxiv.1206.2436
openalex publication_date 2012/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The PCP Theorem is one of the most stunning results in computational complexity theory, a culmination of a series of results regarding proof checking it exposes some deep structure of computational problems. As a surprising side-effect, it also gives strong non-approximability results. In this paper we initiate the study of proof checking within the scope of Parameterized Complexity. In particular we adapt and extend the PCP[n log log n, n log log n] result of Feige et al. to several parameterized classes, and discuss some corollaries.