Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR03-019 | 8th June 2003 00:00

Bounds on 2-Query Codeword Testing. Revision of: TR03-019

RSS-Feed




Revision #1
Authors: Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
Accepted on: 8th June 2003 00:00
Downloads: 1627
Keywords: 


Abstract:


Paper:

TR03-019 | 3rd April 2003 00:00

Bounds on 2-Query Codeword Testing.





TR03-019
Authors: Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
Publication: 3rd April 2003 14:15
Downloads: 1826
Keywords: 


Abstract:


We present upper bounds on the size of codes that are locally
testable by querying only two input symbols. For linear codes, we
show that any $2$-locally testable code with minimal distance
$\delta n$ over a finite field $F$ cannot have more than
$|F|^{3/\delta}$ codewords. This result holds even for testers
with two-sided error. For general (non-linear) codes we obtain the
exact same bounds on the code size as a function of the minimal
distance, but our bounds apply only for binary alphabets and
one-sided error testers (i.e. with perfect completeness). Our
bounds are obtained by examining the graph induced by the set of
possible pairs of queries made by a codeword tester on a given
code. We also demonstrate the tightness of our upper bounds and
the essential role of certain parameters.



ISSN 1433-8092 | Imprint