Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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

Speaker: Andrew Drucker (IAS Princeton)
Title: On the Success Probability of Polynomial-Time SAT Solvers
Date: Thursday 6 March 2014
Time: 16:00-17:00
Location: CWI room L017, Science Park 123, Amsterdam

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

Please note that this newsitem has been archived, and may contain outdated information or links.