ECCC-Report TR16-042https://eccc.weizmann.ac.il/report/2016/042Comments and Revisions published for TR16-042en-usFri, 25 Nov 2016 17:55:33 +0200
Revision 2
| Universal Locally Testable Codes |
Tom Gur,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/042#revision2We 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.Fri, 25 Nov 2016 17:55:33 +0200https://eccc.weizmann.ac.il/report/2016/042#revision2
Revision 1
| Universal Locally Testable Codes |
Tom Gur,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/042#revision1We 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.Mon, 15 Aug 2016 08:05:12 +0300https://eccc.weizmann.ac.il/report/2016/042#revision1
Paper TR16-042
| Universal Locally Testable Codes |
Tom Gur,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/042We 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.Sat, 19 Mar 2016 13:34:06 +0200https://eccc.weizmann.ac.il/report/2016/042