Universal locally testable codes (Universal-LTCs), recently introduced in our companion paper [GG16], 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" (Universal-LVCs). A Universal-LVC $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]$, 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 Universal-LVCs of block length $\tilde O(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 $\tilde O(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 Universal-LVC, 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 Universal-LVC for CSP functions.
various expositional improvements
Universal locally testable codes (Universal-LTCs), recently introduced in our companion paper [GG16], 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" (Universal-LVCs). A Universal-LVC $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]$, 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 Universal-LVCs of block length $\tilde O(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 $\tilde O(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 Universal-LVC, 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 Universal-LVC for CSP functions.
Fixed an inaccuracy in the proof of Theorem 4.2.
Universal locally testable codes (Universal-LTCs), recently introduced in our companion paper [GG16], 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" (Universal-LVCs). A Universal-LVC $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]$, 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 Universal-LVCs of block length $\tilde O(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 $\tilde O(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 Universal-LVC, 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 Universal-LVC for CSP functions.
As stated in the paper, this is a companion paper that follows TR16-042 (Revision 2), which deals with uLTCs. The original posting of TR16-042 contained both papers, but we just posted a revision that contains only the uLTC part, leaving the uLVC part to the current TR.
