Bounds on 2-Query Codeword Testing.
Eli Ben‐Sasson, Oded Goldreich, Madhu Sudan · 2003
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 δn over any finite field F cannot have more than |F | 3/δ 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. 1