Locally Testable Codes and PCPs of Almost-Linear Length 655
BEN-SASSON,E.,AND SUDAN, M. 2005. Short PCPs with poly-log rate and query complexity. In Pro-
ceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, New York, 266–275.
B
EN-SASSON, E., SUDAN,M.VADHAN, S., AND WIGDERSON, A. 2003b. Randomness-efficient low degree
tests and short PCPs via biased sets. In Proceedings of the 35th ACM Symposium on the Theory of
Computing. ACM, New York, 612–621.
B
LUM, M., LUBY,M.,AND RUBINFELD, R. 1993. Self-testing/correcting with applications to numerical
problems. J. Comput. Syst. Sci. 47, 3, 549–595.
C
REIGNOU, N., KHANNA, S., AND SUDAN, M. 2001. Complexity Classifications of Boolean Constraint
Satisfaction Problems. SIAM Press, Philadeplhia, PA.
D
INUR, I. 2006. The PCP theorem by gap amplification. In Proceedings of the 38th ACM Symposium on
the Theory of Computing. ACM, New York, 241–250.
D
INUR,I.,AND REINGOLD, O. 2004. Assignment-testers: Towards a combinatorial proof of the PCP-
theorem. In Proceedings of the 45th Annual IEEE Symposium on on Foundations of Computer Science.
IEEE. Computer Society Press, Los Alamitos, CA, 155–164.
E
VEN, S., SELMAN,A.L.,AND YACOBI, Y. 1984. The complexity of promise problems with applications
to public-key cryptography. Info. Control 61, 2 (May), 159–173.
F
EIGE, U., GOLDWASSER,S.LOV
´
ASZ, L., SAFRA, S., AND SZEGEDY, M. 1996. Interactive proofs and the
hardness of approximating cliques. J. ACM, 43, 268–292.
F
ORNEY,JR., G. D. 1966. Concatenated Codes. MIT Press, Cambridge, MA.
F
RIEDL, K., AND SUDAN, M. 1995. Some improvements to low-degree tests. In Proceedings of the 3rd
Annual Israel Symposium on Theory and Computing Systems, (Washington, DC).
G
OLDREICH, O., GOLDWASSER, S., AND D. RON. 1998. Property testing and its connection to learning
and approximation. J. ACM, 653–750.
G
OLDREICH,O,KARLOFF, H., SCHULMAN,L.J.,AND TREVISAN, L. 2002. Lower bounds for linear locally
decodable codes and private information retrieval. In the Proceedings of the 17th IEEE Conference on
Computational Complexity. IEEE, Computer Society Press, Los Alamitos, CA, 175–183.
G
OLDREICH, O., AND SUDAN, M. 2002. Locally testable codes and PCPs of almost-linear length tech.
Rep. TR02-050, ECCC.
H
ARSHA,P.,AND SUDAN. M. 2000. Small PCPs with low query complexity. Computat. Complex. 9,
(3–4), 157–201.
H
˚
A
STAD
, J. 1999. Clique is hard to approximate within n
1−
. Acta Math. 182, 105–142.
K
ATZ,J.,AND TREVISAN, L. 2000. On the efficiency of local decoding procedures for error-correcting
codes. In STOC’00: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. ACM,
New York, 80–86.
K
IWI, M. 2003. Algebraic testing and weight distribution of dual codes. TR97-010.
M
OTWANI,R.,AND RAGHAVAN, P. 1995. Randomized Algorithms. Cambridge University Press.
P
OLISHCHUK, A., AND SPIELMAN, D. A. 1994. Nearly-linear size holographic proofs. In Proceedings of
the 26th Annual ACM Symposium on the Theory of Computing, ACM, New York, 194–203.
R
AZ
,R.,AND SAFRA, S. 1997. A sub-constant error-probability low-degree test, and a sub-constant
error-probability PCP characterization of NP. In Proceedings of the 29th Annual ACM Symposium on the
Theory of Computing. ACM, New York, 475–484.
R
UBINFELD,R.,AND SUDAN, M. 1996. Robust characterization of polynomials with applications to
program testing. SIAM J. Comput. 25, (2) (Apr.), 252–271.
RECEIVED FEBRUARY 2004; REVISED FEBRUARY 2005 AND MARCH 2006; ACCEPTED MARCH 2006
Journal of the ACM, Vol. 53, No. 4, July 2006.