Good locally testable codes

From To appear in forthcoming issues 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.

Keywords
, , ,
Mathematical Subject Classification

Primary 2020: , ,

Milestones
Received: 2022-08-09
Revised: 2025-03-03
Accepted: 2025-04-24

Authors

Irit Dinur

Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel

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

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

Shahar Mozes

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