On the AND- and OR-Conjectures: Limits to Efficient Preprocessing

Computer Science/Discrete Mathematics Seminar II
Topic:On the AND- and OR-Conjectures: Limits to Efficient Preprocessing
Speaker:Andrew Drucker
Affiliation:Massachusetts Institute of Technology; Member, School of Mathematics
Date:Tuesday, October 16
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csmd/drucker2012Oct16

One of the major insights of the ``fixed-parameter tractability’’ (FPT) approach to algorithm design is that, for many NP-hard problems, it is possible to efficiently *shrink* instances which have some underlying simplicity. This preprocessing can be a powerful first step toward solving such instances. At the same time, many other NP-hard problems have resisted efficient preprocessing. The ``AND-‘’ and ``OR-conjectures’’ of Bodlaender, Downey, Fellows, and Hermelin (JCSS 2009) gave a unified explanation of the hardness of many such problems. Since their work, one goal has been to provide more standard complexity-theoretic evidence for these conjectures. After introducing the relevant background, I will describe recent progress in this area. Based on the paper ``New Limits to Classical and Quantum Instance Compression.’’