DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.70

Good Locally Testable Codes with Small Alphabet and Small Query Size

Authors: Uriya A. First and Stav Lazarovici

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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.

Cite as

Uriya A. First and Stav Lazarovici. Good Locally Testable Codes with Small Alphabet and Small Query Size. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 70:1-70:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{first_et_al:LIPIcs.APPROX/RANDOM.2026.70,
  author =	{First, Uriya A. and Lazarovici, Stav},
  title =	{{Good Locally Testable Codes with Small Alphabet and Small Query Size}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{70:1--70:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.70},
  URN =		{urn:nbn:de:0030-drops-277877},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.70},
  annote =	{Keywords: error correcting code, locally testable code, property testing}
}

Search Results

Documents authored by First, Uriya A.

Good Locally Testable Codes with Small Alphabet and Small Query Size

Abstract

Cite as

Thanks for your feedback!

Could not send message