Low-degree test with polynomially small error
From MaRDI portal
Publication:2410685
DOI10.1007/s00037-016-0149-4zbMath1378.68052MaRDI QIDQ2410685
Publication date: 18 October 2017
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-016-0149-4
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20: Randomized algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- PCP characterizations of NP: toward a polynomially-small error-probability
- Non-deterministic exponential time has two-prover interactive protocols
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Improved low-degree testing and its applications
- Small Value Parallel Repetition for General Games
- Proof verification and the hardness of approximation problems
- Randomness conductors and constant-degree lossless expanders
- Two-query PCP with subconstant error
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Sub-Constant Error Low Degree Test of Almost-Linear Size
- Probabilistic checking of proofs
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- New Direct-Product Testers and 2-Query PCPs
- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- Expanders that beat the eigenvalue bound
- Efficient probabilistically checkable proofs and applications to approximations
- Analytical approach to parallel repetition
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
