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 #3 to TR12-112 | 24th December 2014 23:53

New Limits to Classical and Quantum Instance Compression

RSS-Feed




Revision #3
Authors: Andrew Drucker
Accepted on: 24th December 2014 23:54
Downloads: 1103
Keywords: 


Abstract:

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



Changes to previous version:

In our main technical reduction (Theorem 7.1), clarified the requirement that the parameter t_1 be polynomially bounded. This had been intended and indicated in the Intro, but was not sufficiently explicit. Similar correction to Thms. 7.4, 7.5, and 8.14 (which is now Thm. 8.19). Various small improvements to the writeup.


Revision #2 to TR12-112 | 20th November 2013 21:43

New Limits to Classical and Quantum Instance Compression





Revision #2
Authors: Andrew Drucker
Accepted on: 20th November 2013 21:43
Downloads: 2401
Keywords: 


Abstract:

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



Changes to previous version:

Small fix/tweak to the new material of Revision #1.


Revision #1 to TR12-112 | 19th November 2013 03:23

New Limits to Classical and Quantum Instance Compression





Revision #1
Authors: Andrew Drucker
Accepted on: 19th November 2013 03:23
Downloads: 2437
Keywords: 


Abstract:

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



Changes to previous version:

Changes: 1. We prove the new result that strong compression for either AND(SAT) or OR(SAT) would imply NP is in coAM.

2. A correction: the techniques used previously to rule out strong compression reductions for F(SAT) with "combining functions" F other than AND, OR do not work for a certain case, namely when F is monotone, depends on all variables, and has very low block sensitivity. (We had erroneously ruled out the existence of such functions.)
We give a new argument to handle F with low block sensitivity, subject to a certain explicitness condition on F. As a by-product we obtain item 1 above. (See Secs. 1.3.1, 7.3, and 9.)


Paper:

TR12-112 | 7th September 2012 03:37

New Limits to Classical and Quantum Instance Compression





TR12-112
Authors: Andrew Drucker
Publication: 7th September 2012 03:57
Downloads: 3356
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint