Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 36 (4), 889-974
- https://doi.org/10.1137/s0097539705446810
Abstract
No abstract availableThis publication has 30 references indexed in Scilit:
- Lower bounds for adaptive locally decodable codesRandom Structures & Algorithms, 2005
- Some 3CNF Properties Are Hard to TestSIAM Journal on Computing, 2005
- The random oracle methodology, revisitedJournal of the ACM, 2004
- Fast approximate probabilistically checkable proofsInformation and Computation, 2004
- Free Bits, PCPs, and Nonapproximability---Towards Tight ResultsSIAM Journal on Computing, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- Simple Constructions of Almost k‐wise Independent Random VariablesRandom Structures & Algorithms, 1992
- Short propositional formulas represent nondeterministic computationsInformation Processing Letters, 1988