Good Locally Testable Codes

Pages 511-553 from Volume 203 (2026), Issue 2 by Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes

Abstract

An explicit construction of locally testable codes of constant rate, constant distance and constant number of queries is given. Hence answering affirmatively the $c^3$-problem.

roblem.

Keywords
, , ,
Mathematical Subject Classification

Primary 2020: Secondary: ,

DOI
https://doi.org/10.4007/annals.2026.203.2.3
Milestones
Received: 9 August 2022
Revised: 3 March 2025
Accepted: 24 April 2025
Published online: 1 March 2026

Authors

Irit Dinur

Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel and School of Mathematics, Institute for Advanced Study, Princeton, NJ, USA

Shai Evra

Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, Israel

Ron Livne

Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, Israel

Alexander Lubotzky

Department of Pure Mathematics, The Weizmann Institute of Science, Rehovot, Israel
Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, Israel

Shahar Mozes

Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, Israel