Smooth and strong PCPs
From MaRDI portal
Publication:2029773
DOI10.1007/s00037-020-00199-3zbMath1485.68101OpenAlexW3119413233MaRDI QIDQ2029773
Publication date: 4 June 2021
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-020-00199-3
probabilistically checkable proofshardness of approximationinteractive and probabilistic proof systems
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- PCP characterizations of NP: toward a polynomially-small error-probability
- Center-based clustering under perturbation stability
- Lower bounds for linear locally decodable codes and private information retrieval
- Lifts, discrepancy and nearly optimal spectral gap
- Optimization, approximation, and complexity classes
- Self-testing/correcting with applications to numerical problems
- Non-interactive proofs of proximity
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Are Stable Instances Easy?
- Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- On the efficiency of local decoding procedures for error-correcting codes
- Locally testable codes and PCPs of almost-linear length
- Combinatorial Construction of Locally Testable Codes
- Two-query PCP with subconstant error
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
- Relaxed Locally Correctable Codes
- On the Power of Relaxed Local Decoding Algorithms
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- Strong Locally Testable Codes with Relaxed Local Decoders
- Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
- Introduction to Property Testing
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- Probabilistically Checkable Proofs of Proximity with Zero-Knowledge
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Locally Decodable Codes
- The PCP theorem by gap amplification
