Spring 2015

Limits to Efficient Preprocessing

Wednesday, April 22nd, 2015 2:30 pm3:00 pm

Add to Calendar

"Kernelization" is an influential paradigm for attacking hard computational problems. Kernelization reductions efficiently preprocess their input to “shrink” it to a smaller, equivalent one. This can be a valuable first step before applying exhaustive-search techniques.

After giving the basic framework of kernelization, I’ll describe my contribution to a line of works showing limits to the power of kernelization for many NP problems (under complexity-theoretic assumptions). To this end, I show that if such problems have a sufficiently strong kernelization reduction, the information bottleneck in the reduction can be exploited to give proofs of unsatisfiability for Boolean formulas.

Based on: [A. Drucker, New Limits to Classical and Quantum Instance Compression. FOCS’12]