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

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)
• BibTeX entry for this article (310 bytes)

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

© 2018 Oded Goldreich and Tom Gur
Licensed under a Creative Commons Attribution License

Volume 2018, Article 2

Article 4

Volume 2018

Published articles