Chicago Journal of Theoretical Computer Science

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
oded DOT goldreich AT weizman DOT ac DOT il


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


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.

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

DOI: 10.4086/cjtcs.2018.003

[] Volume 2018, Article 2 [] Article 4
[back] Volume 2018 [back] Published articles
[CJCTS home]