Two-query PCP with subconstant error
From MaRDI portal
Publication:3579632
DOI10.1145/1754399.1754402zbMath1327.68110OpenAlexW2153413398MaRDI QIDQ3579632
Publication date: 9 August 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1754399.1754402
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (34)
Succinct non-interactive arguments via linear interactive proofs ⋮ Low-degree test with polynomially small error ⋮ Time-approximation trade-offs for inapproximable problems ⋮ New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sparsification and subexponential approximation ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ Relaxed Locally Correctable Codes ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Shorter arithmetization of nondeterministic computations ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Easy capacitated facility location problems, with connections to lot-sizing ⋮ Improved approximation algorithms for projection games ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ New tools and connections for exponential-time approximation ⋮ Unnamed Item ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Smooth and strong PCPs ⋮ Unnamed Item ⋮ Satisfying Degree-d Equations over GF[2 n] ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ A combination of testability and decodability by tensor products ⋮ Unnamed Item ⋮ On subexponential and FPT-time inapproximability ⋮ Unnamed Item ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs
This page was built for publication: Two-query PCP with subconstant error
