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.
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.
Abstract of the companion paper
Material available on-line
Back to
either Oded Goldreich's homepage
or general list of papers.