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.

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.

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.

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

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

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.