Bounds on 2-Query Codeword Testing

Webpage for a paper by Ben-Sasson, Goldreich, and Sudan


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.

Material available on-line


Back to either Oded Goldreich's homepage. or general list of papers.