Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-138 | 14th December 2009 22:37

Bounds on 2-Query Locally Testable Codes with Affine Tests

RSS-Feed




TR09-138
Authors: Gillat Kol, Ran Raz
Publication: 15th December 2009 04:59
Downloads: 2991
Keywords: 


Abstract:

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is the tested word and a,b,c are in F.

We show that such LTCs, with high minimal distance, must be of constant size. Specifically, we show that every 2-query LTC with affine tests over F, that has minimal distance at least 9/10, completeness at least $1-\epsilon$, and soundness at most $1-3\epsilon$, is of size at most |F|.

Our main motivation in studying LTCs with affine tests is the Unique Games Conjecture (UGC), and the close connection between LTCs and PCPs. We mention that all known PCP constructions use LTCs with corresponding properties as building blocks, and that many of the LTCs used in PCP constructions are affine. Furthermore, the UGC was shown to be equivalent to the UGC with affine tests [KKMO07], thus the UGC implies the existence of a low-error 2-query PCP with affine tests.



ISSN 1433-8092 | Imprint