Universal Locally Testable Codes

Webpage for a paper by Oded Goldreich and Tom Gur


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:\bitset^k \to \bitset^n$ for a family of functions $F = \left\{f_i:\bitset^k\to\bitset\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 $\tildeO(M\cdot s)$ for any family $F$ of $M$ functions such that every $f\in 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 $F$ such that every $f,f' \in\mathcal{F}$ disagree on a constant fraction of their domain.

Note (Nov'16): This work previously appeared as a part of our technical report, which contained the foregoing results regarding ULTCs as well as results regarding ``universal locally verifiable codes''. Since this combination caused the latter notion and results to be missed, we chose to split the original version into two parts. The current part contains the material regarding ULTCs. The part regarding ULVCs appears in a companion paper.

Abstract of the companion paper

We also consider a variant of ULTCs wherein the testing procedures are also given free access to a short proof, akin the MAPs of Gur and Rothblum (ITCS 2015). We call such codes ``universal locally \emph{verifiable} codes" (ULVCs). We show ULVCs of length $\tildeO(n^2)$ for $t$-ary constraint satisfaction problems ($t$-CSP) over $k$ variables, with proof length and query complexity $\tildeO(n^{2/3})$, where $t=O(1)$ and $n\ge k$ is the number of constraints in the CSP instance. In addition, we prove a lower bound of $p \cdot q = \tilde\Omega(k)$ for every polynomial length ULVC for CSPs (over $k$ variables) having proof complexity $p$ and query complexity $q$.

Lastly, we give an application for \emph{interactive proofs of proximity} (IPP), introduced by Rothblum et al. (STOC 2013), which are interactive proof systems wherein the verifier queries only a sublinear number of input bits and soundness only means that, with high probability, the input is close to an accepting input. We show that using a small amount of interaction, our ULVC for CSP can be, in a sense, ``emulated" by an IPP, yielding a 3-round IPP for CSP with sublinear communication and query complexity.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.