#

### Volume 2018

#### Article 3

Published by the Department of Computer Science, The University of Chicago.

#### 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" (*ULTC*s).
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)
**BibTeX** entry for this
article (310 bytes)

Submitted June 2, 2017, revised June 20, 2018,
published August 7, 2018.

Volume 2018, Article 2
Article 4

Volume 2018
Published articles