On Dinur’s proof of the PCP theorem
From MaRDI portal
Publication:3430210
DOI10.1090/S0273-0979-06-01143-8zbMath1112.68117WikidataQ62065913 ScholiaQ62065913MaRDI QIDQ3430210
Jaikumar Radhakrishnan, Madhu Sudan
Publication date: 21 March 2007
Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Hyper-regular graphs and high dimensional expanders ⋮ Colouring, constraint satisfaction, and complexity ⋮ Expander graphs -- both local and global ⋮ Revisiting alphabet reduction in Dinur’s PCP. ⋮ Function simulation, graph grammars and colourings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Eigenvalues and expanders
- Optimization, approximation, and complexity classes
- Self-testing/correcting with applications to numerical problems
- On the power of multi-prover interactive protocols
- Linearity testing in characteristic two
- Proof verification and the hardness of approximation problems
- Expander graphs and their applications
- Simple PCPs with poly-log rate and query complexity
- The Knowledge Complexity of Interactive Proof Systems
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- Efficient probabilistically checkable proofs and applications to approximations
- Some optimal inapproximability results
- The complexity of theorem-proving procedures
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- The PCP theorem by gap amplification
