Simple analysis of graph tests for linearity and PCP
- 6 January 2003
- journal article
- Published by Wiley in Random Structures & Algorithms
- Vol. 22 (2), 139-160
- https://doi.org/10.1002/rsa.10068
Abstract
No abstract availableKeywords
Funding Information
- NSF (CCR-9987077, CCR-9987845)
This publication has 15 references indexed in Scilit:
- The Non-approximability of Non-Boolean PredicatesLecture Notes in Computer Science, 2001
- Linear-Consistency TestingPublished by Elsevier BV ,2001
- The Probabilistic MethodPublished by Wiley ,2000
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- 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
- Linearity testing in characteristic twoIEEE Transactions on Information Theory, 1996
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- On sequences of integers containing no arithmetic progressionČasopis pro pěstování matematiky a fysiky, 1938