Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers

Andrew Drucker
Member, School of Mathematics
May 13, 2013

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.