Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

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

Revision #1
Authors: Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
Accepted on: 8th June 2003 00:00
Downloads: 1154
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: 1244
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