The PCP theorem by gap amplification
From MaRDI portal
Publication:5900521
DOI10.1145/1236457.1236459zbMath1292.68074OpenAlexW2038691311WikidataQ56047330 ScholiaQ56047330MaRDI QIDQ5900521
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1236457.1236459
Related Items (87)
Shift lifts preserving Ramanujan property ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ Quantum Locally Testable Codes ⋮ Expander Construction in VNC1 ⋮ Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries ⋮ An algebraic proof of the real number PCP theorem ⋮ A PCP theorem for interactive proofs and applications ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Linear-size constant-query IOPs for delegating computation ⋮ Generating sets for the multiplicative groups of algebras over finite fields and expander graphs ⋮ An Algebraic Proof of the Real Number PCP Theorem ⋮ Bridging a Small Gap in the Gap Amplification of Assignment Testers ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ Max-3-Lin over non-abelian groups with universal factor graphs ⋮ Public Bayesian persuasion: being almost optimal and almost persuasive ⋮ Unnamed Item ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ Erasures versus errors in local decoding and property testing ⋮ Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\) ⋮ Succinct arguments for RAM programs via projection codes ⋮ Unnamed Item ⋮ A toolbox for barriers on interactive oracle proofs ⋮ Proof of avoidability of the quantum first-order transition in transverse magnetization in quantum annealing of finite-dimensional spin glasses ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Sparsification and subexponential approximation ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Colouring, constraint satisfaction, and complexity ⋮ A survey on the structure of approximation classes ⋮ A structure theorem for almost low-degree functions on the slice ⋮ When polynomial approximation meets exact computation ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Testing Odd Direct Sums Using High Dimensional Expanders ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Shorter arithmetization of nondeterministic computations ⋮ Composition of semi-LTCs by two-wise tensor products ⋮ The interval constrained 3-coloring problem ⋮ A PCP Characterization of AM ⋮ When polynomial approximation meets exact computation ⋮ Revisiting alphabet reduction in Dinur’s PCP. ⋮ Shorter unentangled proofs for ground state connectivity ⋮ Symmetric LDPC codes and local testing ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Best-order streaming model ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Symmetric LDPC Codes and Local Testing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Smooth and strong PCPs ⋮ Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs ⋮ Product-state approximations to quantum states ⋮ Submodular unsplittable flow on trees ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Dense Locally Testable Codes Cannot Have Constant Rate and Distance ⋮ Efficient Probabilistically Checkable Debates ⋮ SPARKs: succinct parallelizable arguments of knowledge ⋮ Almost Transparent Short Proofs for NPℝ ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Every Set in P Is Strongly Testable Under a Suitable Encoding ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ High Dimensional Random Walks and Colorful Expansion ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ A combination of testability and decodability by tensor products ⋮ On Dinur’s proof of the PCP theorem ⋮ On subexponential and FPT-time inapproximability ⋮ Unnamed Item ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity ⋮ Spartan: efficient and general-purpose zkSNARKs without trusted setup ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ A parallel repetition theorem for entangled projection games ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs ⋮ Direct Sum Testing ⋮ A PCP of proximity for real algebraic polynomials
This page was built for publication: The PCP theorem by gap amplification
