ECCC-Report TR16-192https://eccc.weizmann.ac.il/report/2016/192Comments and Revisions published for TR16-192en-usThu, 25 Jan 2018 11:39:25 +0200
Revision 2
| Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP |
Tom Gur,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/192#revision2Universal 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.Thu, 25 Jan 2018 11:39:25 +0200https://eccc.weizmann.ac.il/report/2016/192#revision2
Revision 1
| Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP |
Tom Gur,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/192#revision1Universal 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.Sat, 10 Dec 2016 17:00:43 +0200https://eccc.weizmann.ac.il/report/2016/192#revision1
Comment 1
| The companion paper (TR16-042) |
Oded Goldreich,
Tom Gur
https://eccc.weizmann.ac.il/report/2016/192#comment1As 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.Mon, 28 Nov 2016 08:58:22 +0200https://eccc.weizmann.ac.il/report/2016/192#comment1
Paper TR16-192
| Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP |
Tom Gur,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/192Universal 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.Fri, 25 Nov 2016 16:40:38 +0200https://eccc.weizmann.ac.il/report/2016/192