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