Linear-consistency testing.

DOI10.1006/jcss.2001.1747zbMath1052.68122OpenAlexW1993625811WikidataQ56959015 ScholiaQ56959015MaRDI QIDQ5946056

Johan T. Håstad, Madhu Sudan, Michael O. Rabin, Yonatan Aumann

Publication date: 2 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1747

zbMATH Keywords

linearity testingprobabilistically checkable proofs

Mathematics Subject Classification ID

General topics in the theory of software (68N01)

Related Items

Simple analysis of graph tests for linearity and PCP, A query efficient non-adaptive long code test with perfect completeness, Breaking the ε-Soundness Bound of the Linearity Test over GF(2)

Cites Work

• Unnamed Item
• Unnamed Item
• Self-testing/correcting with applications to numerical problems
• Linearity testing in characteristic two
• Proof verification and the hardness of approximation problems
• A PCP characterization of NP with optimal amortized query complexity
• Probabilistic checking of proofs
• Designing programs that check their work
• A Parallel Repetition Theorem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Positive linear programming, parallel approximation and PCP's
• Efficient probabilistically checkable proofs and applications to approximations