2026-09-10T09:44:37Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:27787 2026-09-09T12:19:39Z ddc:004 open_access
Good Locally Testable Codes with Small Alphabet and Small Query Size First, Uriya A. Lazarovici, Stav error correcting code locally testable code property testing Ben-Sasson, Goldreich and Sudan [Ben-Sasson et al., 2003] showed that a binary error correcting code admitting a 2-query tester cannot be good, i.e., it cannot have both linear distance and constant rate. They also showed that there are no good codes if the alphabet is a finite field 𝔽, the code is 𝔽-linear, and the 2-query tester is 𝔽-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 𝔽-linear LTCs, and for every 𝔽-vector space V of dimension greater than 1, there are good 2-query LTCs with alphabet V whose tester is 𝔽-linear. This completely solves, for every q β‰₯ 2 and alphabet (resp. 𝔽-vector space) Ξ£, the question of whether there is a good q-query LTC (resp. 𝔽-LTC) with alphabet Ξ£. Our proof builds on the recent good 2-query 𝔽-LTCs of the first author and Kaufman [First and Kaufman, 2024], by establishing a general method for reducing the alphabet size of a good low-query LTC. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Uriya A. First and Stav Lazarovici 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.70 urn:nbn:de:0030-drops-277877 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.70 eng https://creativecommons.org/licenses/by/4.0/legalcode