### Volume 2018

#### Universal Locally Testable Codes

Oded Goldreich
Faculty of Mathematics and Computer Science
Weizmann Institute of Science
Israel
oded DOT goldreich AT weizman DOT ac DOT il

and

Tom Gur
Department of Electrical Engineering and Computer Science
University of California, Berkeley
Berkeley, CA, USA
tom DOT gur AT berkeley DOT edu

August 7, 2018

#### Abstract

We initiate a study of universal locally testable codes" (ULTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a ULTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \left\{ f_i : \{0,1\}^k \to \{0,1\} \right\}_{i \in [M]}$ is a code such that for every $i \in [M]$ the subcode $\{ C(x) \: : \: f_i(x) = 1 \}$ is locally testable. We show a canonical" $O(1)$-local ULTC of length $\tilde O(M\cdot s)$ for any family $\mathcal{F}$ of $M$ functions such that every $f\in\mathcal{F}$ can be computed by a circuit of size $s$, and establish a lower bound of the form $n=M^{1/O(k)}$, which can be strengthened to $n=M^{\Omega(1)}$ for any $\mathcal{F}$ such that every $f,f' \in\mathcal{F}$ disagree on a constant fraction of their domain.

• The article: PDF (344 KB)
• Source material: ZIP (104 KB)