We initiate a study of ``universal locally testable codes" (Universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a Universal-LTC $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 Universal-LTC 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.

This work appeared previously as a part of the first version of this technical report, which contained results regarding Universal-LTCs as well as results regarding a related notion called ``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 Universal-LTCs. The part regarding universal locally verifiable codes appears in a companion paper (ECCC TR16-192).

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{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 universal-LTC 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.

We also consider a variant of universal-LTCs 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 verifiable codes" (universal-LVCs). We show universal-LVCs of length $\tilde{O}(n^2)$ for $t$-ary constraint satisfaction problems ($t$-CSP) over $k$ variables, with proof length and query complexity $\tilde{O}(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 universal-LVC for CSPs (over $k$ variables) having proof complexity $p$ and query complexity $q$.

Lastly, we give an application for 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 universal-LVC for CSP can be, in a sense, ``emulated" by an IPP, yielding a $3$-round IPP for CSP with sublinear communication and query complexity.

Minor corrections

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{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 universal-LTC 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.

We also consider a variant of universal-LTCs 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 verifiable codes" (universal-LVCs). We show universal-LVCs of length $\tilde{O}(n^2)$ for $t$-ary constraint satisfaction problems ($t$-CSP) over $k$ variables, with proof length and query complexity $\tilde{O}(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 universal-LVC for CSPs (over $k$ variables) having proof complexity $p$ and query complexity $q$.

Lastly, we give an application for 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 universal-LVC for CSP can be, in a sense, ``emulated" by an IPP, yielding a $3$-round IPP for CSP with sublinear communication and query complexity.