New Limits to Classical and Quantum Instance Compression

Andrew Drucker

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 ψ1,⋯,ψt, we must determine if at least one ψj is satisfiable. An OR-compression scheme for SAT is a polynomial-time reduction that maps (ψ1,⋯,ψt) to a string z, such that z lies in some “target” language L' if and only if Vj[ψj ∈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 = maxj |ψ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 C 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 ⊆ 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-compres- ion 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 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.
Original languageEnglish
Title of host publication53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
Publication statusPublished - 2012


Dive into the research topics of 'New Limits to Classical and Quantum Instance Compression'. Together they form a unique fingerprint.

Cite this