Good Locally Testable Codes with Small Alphabet and Small Query Size

Ben-Sasson, Goldreich and Sudan showed that a binary error correcting code admitting a 2-query tester cannot be good, i. e. , it cannot have both linear distance and positive rate. The same holds when the alphabet is a finite field F, the code is F-linear, and the 2-query tester is F-linear. We show that those are essentially the only limitations on the existence of good locally testable codes (LTCs). That is, there are good 2-query LTCs on any alphabet with more than 2 letters, and good 3-query LTCs with a binary alphabet. Similarly, there are good 3-query F-linear LTCs, and for every F-vector space V of dimension greater than 1, there are good 2-query LTCs with alphabet V whose tester is F-linear. This completely solves, for every q 2 and alphabet (resp. F-vector space) Σ, the question of whether there is a good q-query LTC (resp. F-LTC) with alphabet Σ. Our proof builds on the recent good 2-query F-LTCs of the first author and Kaufman, by establishing a general method for reducing the alphabet size of a low-query LTC.