Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-042 | 25th November 2016 17:55

Universal Locally Testable Codes

RSS-Feed




Revision #2
Authors: Oded Goldreich, Tom Gur
Accepted on: 25th November 2016 17:55
Downloads: 143
Keywords: 


Abstract:

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.



Changes to previous version:

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).


Revision #1 to TR16-042 | 15th August 2016 08:05

Universal Locally Testable Codes





Revision #1
Authors: Oded Goldreich, Tom Gur
Accepted on: 15th August 2016 08:05
Downloads: 216
Keywords: 


Abstract:

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.



Changes to previous version:

Minor corrections


Paper:

TR16-042 | 19th March 2016 12:41

Universal Locally Testable Codes





TR16-042
Authors: Oded Goldreich, Tom Gur
Publication: 19th March 2016 13:34
Downloads: 329
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint