ECCC-Report TR12-112https://eccc.weizmann.ac.il/report/2012/112Comments and Revisions published for TR12-112en-usWed, 24 Dec 2014 23:54:08 +0200
Revision 3
| New Limits to Classical and Quantum Instance Compression |
Andrew Drucker
https://eccc.weizmann.ac.il/report/2012/112#revision3Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression \ scheme$ for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some "target'' language $L'$ if and only if $\ \bigvee_j \ [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is $strong$ if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$.
Strong compression for SAT seems unlikely. Work of Harnik and Naor (FOCS '06/SICOMP '10) and Bodlaender, Downey, Fellows, and Hermelin (ICALP '08/JCSS '09) showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam (STOC '08/JCSS '11) showed that if SAT is strongly OR-compressible, then $NP \subseteq coNP/poly$. Finding similar evidence against AND-compression was left as an open question.
We provide such evidence: we show that strong AND- $or$ OR-compression for SAT would imply $non-uniform, \ statistical \ zero-knowledge \ proofs$ for SAT---an even stronger and more unlikely consequence than $NP \subseteq coNP/poly$. Our method applies against $probabilistic$ compression schemes of sufficient "quality'' with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of $quantum \ instance \ compression$, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, "preserves the answer'' to the input instance.
The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to "disguise'' information being fed into a compressive mapping; we believe this method may find other applications.Wed, 24 Dec 2014 23:54:08 +0200https://eccc.weizmann.ac.il/report/2012/112#revision3
Revision 2
| New Limits to Classical and Quantum Instance Compression |
Andrew Drucker
https://eccc.weizmann.ac.il/report/2012/112#revision2Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression \ scheme$ for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some "target'' language $L'$ if and only if $\ \bigvee_j \ [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is $strong$ if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$.
Strong compression for SAT seems unlikely. Work of Harnik and Naor (FOCS '06/SICOMP '10) and Bodlaender, Downey, Fellows, and Hermelin (ICALP '08/JCSS '09) showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam (STOC '08/JCSS '11) showed that if SAT is strongly OR-compressible, then $NP \subseteq coNP/poly$. Finding similar evidence against AND-compression was left as an open question.
We provide such evidence: we show that strong AND- $or$ OR-compression for SAT would imply $non-uniform, \ statistical \ zero-knowledge \ proofs$ for SAT---an even stronger and more unlikely consequence than $NP \subseteq coNP/poly$. (By a different argument, we also show such compression would imply the $uniform$ collapse $NP \subseteq coAM$.) Our method applies against $probabilistic$ compression schemes of sufficient "quality'' with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of $quantum \ instance \ compression$, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, "preserves the answer'' to the input instance.
The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to "disguise'' information being fed into a compressive mapping; we believe this method may find other applications.Wed, 20 Nov 2013 21:43:52 +0200https://eccc.weizmann.ac.il/report/2012/112#revision2
Revision 1
| New Limits to Classical and Quantum Instance Compression |
Andrew Drucker
https://eccc.weizmann.ac.il/report/2012/112#revision1Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression \ scheme$ for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some "target'' language $L'$ if and only if $\ \bigvee_j \ [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is $strong$ if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$.
Strong compression for SAT seems unlikely. Work of Harnik and Naor (FOCS '06/SICOMP '10) and Bodlaender, Downey, Fellows, and Hermelin (ICALP '08/JCSS '09) showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam (STOC '08/JCSS '11) showed that if SAT is strongly OR-compressible, then $NP \subseteq coNP/poly$. Finding similar evidence against AND-compression was left as an open question.
We provide such evidence: we show that strong AND- $or$ OR-compression for SAT would imply $non-uniform, \ statistical \ zero-knowledge \ proofs$ for SAT---an even stronger and more unlikely consequence than $NP \subseteq coNP/poly$. (By a different argument, we also show such compression would imply $NP \subseteq coAM$.) Our method applies against $probabilistic$ compression schemes of sufficient "quality'' with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of $quantum \ instance \ compression$, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, "preserves the answer'' to the input instance.
The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to "disguise'' information being fed into a compressive mapping; we believe this method may find other applications.Tue, 19 Nov 2013 03:23:32 +0200https://eccc.weizmann.ac.il/report/2012/112#revision1
Paper TR12-112
| New Limits to Classical and Quantum Instance Compression |
Andrew Drucker
https://eccc.weizmann.ac.il/report/2012/112Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression \ scheme$ for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some "target'' language $L'$ if and only if $\ \bigvee_j \ [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is $strong$ if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$.
Strong compression for SAT seems unlikely. Work of Harnik and Naor (FOCS '06/SICOMP '10) and Bodlaender, Downey, Fellows, and Hermelin (ICALP '08/JCSS '09) showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam (STOC '08/JCSS '11) showed that if SAT is strongly OR-compressible, then $NP \subseteq coNP/poly$. Finding similar evidence against AND-compression was left as an open question.
We provide such evidence: we show that strong AND- $or$ OR-compression for SAT would imply $non-uniform, \ statistical \ zero-knowledge \ proofs$ for SAT---an even stronger and more unlikely consequence than $NP \subseteq coNP/poly$. Our method applies against $probabilistic$ compression schemes of sufficient "quality'' with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of $quantum \ instance \ compression$, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, "preserves the answer'' to the input instance.
The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to "disguise'' information being fed into a compressive mapping; we believe this method may find other applications.Fri, 07 Sep 2012 03:57:35 +0300https://eccc.weizmann.ac.il/report/2012/112