"New Limits to Instance Compression for Hard Problems"

Andrew Drucker

MIT

Monday, May 14th, 2012, 2:00 pm

EBU3B, Room 4140

Abstract

Given an instance of a decision problem that is too difficult to solve outright, we may aim for the more limited goal of compressing that instance into a smaller, equivalent instance of the same or a different problem. Studying the power and limits of instance compression involves an intriguing interplay between computational and information-theoretic ideas.

As a representative problem, say we are given a Boolean formula Psi over n variables, and of size m >> n, and we want to determine if Psi is satisfiable. Can we efficiently reduce this question to an equivalent problem instance of size poly(n), independent of m? Harnik and Naor (FOCS '06) and Bodlaender et al. (ICALP '08) showed that this question is quite significant for cryptography and fixed-parameter tractability theory. Fortnow and Santhanam (STOC '08) gave a negative answer for deterministic compression, assuming that NP is not contained in coNP/poly.

We will describe new and improved evidence against efficient instance compression schemes. Our method applies to probabilistic compression for SAT, and also gives the first evidence against deterministic compression for a number of problems. To prove our results, we exploit the information bottleneck of an instance compression scheme, using a new method to "disguise" information being fed into a compressive mapping.

Short biography

Andrew Drucker is a PhD student in EECS at MIT, expecting to graduate June 2012. His advisor is Scott Aaronson. He has broad research interests, with an emphasis on computational complexity---the study of the inherent limits of efficient computation."