Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers

Speaker: Andrew Drucker , Institute for Advanced Study

Date: Tuesday, December 10, 2013

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Scott Aaronson

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/375

Speaker URL: None

Speaker Photo:
None

Reminders to: toc@csail.mit.edu, seminars@lists.csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers

Abstract: In this talk I will describe nondeterministic reductions which yield new direct product theorems (DPTs) for Boolean circuits. In our theorems one assumes that a function F is "mildly hard" against *nondeterministic* circuits of some size s(n), and concludes that the t-fold direct product F^t is "extremely hard" against probabilistic circuits of only polynomially smaller size s'(n). The main advantage of these results compared with previous DPTs is the strength of the size bound in our conclusion. As an application, we show that if NP is not in coNP/poly then, for every PPT 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. This furthers a project of Paturi and Pudlák [STOC'10].

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2013.

Created by Holly A Jones Email at Tuesday, November 19, 2013 at 3:22 PM.