Universal locally testable codes ULTCs, recently introduced in our companion paper, are codes that admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. In this work, we initiate the study of the NP analogue of these codes, wherein the testing procedures are also given free access to a short proof, akin the MA proofs of proximity of Gur and Rothblum (ITCS 2015). We call such codes ``universal locally verifiable codes" (ULVCs). A ULVC $C:\bitset^k \to \bitset^n$ for a family of functions $\mathcal{F} = \left\{ f_i : \bitset^k \to \bitset \right\}_{i \in [M]}$ is a code such that for every $i \in [M]$, membership in the subcode $\{ C(x):f_i(x) = 1\}$ can be verified locally given an explicit access to a short (sublinear length) proof.
We show ULVCs of block length $\tildeO(n^2)$ for the family of all functions expressible by $t$-ary constraint satisfaction problems ($t$-CSP) over $n$ constraints and $k$ variables, with proof length and query complexity $\tildeO(n^{2/3})$, where $t=O(1)$ and $n\ge k$. In addition, we prove a lower bound of $p \cdot q = \tilde\Omega(k)$ for every polynomial length ULVC, having proof complexity $p$ and query complexity $q$, for such CSP functions.
Lastly, we give an application for interactive proofs of proximity (IPP), introduced by Rothblum, Vadhan, and Wigderson (STOC 2013), which are interactive proof systems wherein the verifier queries only a sublinear number of input bits to the end of asserting that, with high probability, the input is close to an accepting input. Specifically, we show a 3-round IPP for the set of assignments that satisfy fixed CSP instances, with sublinear communication and query complexity, which we derive from our ULVC for CSP functions.
Note (Nov'16):
This work previously appeared as a part of our technical report,
which contained the foregoing results regarding ULVCs and IPPs
as well as results regarding ``universal locally testable codes''.
Since this combination caused the former 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 ULTCs appears in a companion paper.
Material available on-line
Back to
either Oded Goldreich's homepage
or general list of papers.