Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-192 | 25th January 2018 11:39

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP

Revision #2
Authors: Oded Goldreich, Tom Gur
Accepted on: 25th January 2018 11:39
Keywords:

Abstract:

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.

Changes to previous version:

various expositional improvements

Revision #1 to TR16-192 | 10th December 2016 17:00

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP

Revision #1
Authors: Oded Goldreich, Tom Gur
Accepted on: 10th December 2016 17:00
Keywords:

Abstract:

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.

Changes to previous version:

Fixed an inaccuracy in the proof of Theorem 4.2.

Paper:

TR16-192 | 25th November 2016 16:12

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP

TR16-192
Authors: Oded Goldreich, Tom Gur
Publication: 25th November 2016 16:40
Keywords:

Abstract:

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.

Comment(s):

Comment #1 to TR16-192 | 28th November 2016 08:58

The companion paper (TR16-042)

Authors: Oded Goldreich, Tom Gur
Accepted on: 28th November 2016 08:58
Keywords:

Comment:

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.

ISSN 1433-8092 | Imprint