6 March 2014, Theoretical Computer Science Seminar, Andrew Drucker (IAS Princeton)

Abstract

In one approach to solving NP-complete problems like SAT, we try to design an efficient randomized algorithm that attempts to guess a solution, and that is guaranteed to have success probability better than truly-random guessing (if a solution exists). Such "intelligent random guessing" is at the core of a number of improved exponential-time algorithms for these problems. This was observed by Paturi and Pudlák [STOC'10], who found evidence for the limitations of such algorithms.

We further this project. We show that a standard hardness assumption (NP not in coNP/poly) implies the following: For every polynomial-time randomized algorithm attempting to produce satisfying assignments to Boolean formulas, there are infinitely many satisfiable instances on which the algorithm's success probability is nearly-exponentially small. Our proof involves new ideas for the study of average-case complexity in the circuit model.

References:
R. Paturi, P. Pudlák, On the Complexity of Circuit Satisfiability. STOC 2010.
A. Drucker, Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers. FOCS 2013.

For more information, please contact c.schaffner at uva.nl