Two-query PCP with subconstant error
From MaRDI portal
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Recommendations
- A PCP characterization of NP with optimal amortized query complexity
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- scientific article; zbMATH DE number 1559563
- Composition of low-error 2-query PCPs using decodable PCPs
Cited in
(43)- Time-approximation trade-offs for inapproximable problems
- Sparsification and subexponential approximation
- Inapproximability results for constrained approximate Nash equilibria
- Easy capacitated facility location problems, with connections to lot-sizing
- Smooth and strong PCPs
- Succinct non-interactive arguments via linear interactive proofs
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- Hardness results for approximate pure Horn CNF formulae minimization
- New tools and connections for exponential-time approximation
- Low-degree test with polynomially small error
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\)
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- Detecting communities is hard (and counting them is even harder)
- New direct-product testers and 2-query PCPs
- Limitation on the Rate of Families of Locally Testable Codes
- Composition of low-error 2-query PCPs using decodable PCPs
- Shorter arithmetization of nondeterministic computations
- On the power of relaxed local decoding algorithms
- Relaxed locally correctable codes
- Fast Reed-Solomon interactive oracle proofs of proximity
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Approximating the orthogonality dimension of graphs and hypergraphs
- QPTAS and subexponential algorithm for maximum clique on disk graphs
- Improved approximation algorithms for projection games
- Parallel repetition of two-prover one-round games: an exposition
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- A combination of testability and decodability by tensor products
- Computational integrity with a public random string from quasi-linear PCPs
- Composition of low-error 2-query PCPs using decodable PCPs
- On the hardness of pricing loss-leaders
- Relaxed locally correctable codes
- Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
- Approximating the orthogonality dimension of graphs and hypergraphs
- scientific article; zbMATH DE number 7650076 (Why is no real title available?)
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Sub-constant error probabilistically checkable proof of almost-linear size
- Asymptotically-good RLCCs with \((\log n)^{2+o(1)}\) queries
- Optimal inapproximability with universal factor graphs
- Stabilizer testing and magic entropy via quantum Fourier analysis
- Regularization of low error PCPs and an application to MCSP
This page was built for publication: Two-query PCP with subconstant error
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579632)
