School of Mathematics

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.

Cryptography and Preventing Collusion in Second Price (Vickery) Auctions

Michael Rabin
Harvard University and Columbia University
April 29, 2013

We present practically efficient methods for proving correctness of announced results of a computation while keeping input and intermediate values information theoretically secret. These methods are applied to solve the long standing problem of preventing collusion in second-price auctions.

Uncertainty Principle

Klim Efremenko
Tel-Aviv University; Member, School of Mathematics
April 23, 2013

Informally, uncertainty principle says that function and its Fourier transform can not be both concentrated. Uncertainty principle has a lot of applications in areas like compressed sensing, error correcting codes, number theory and many others. In this talk we will try to survey different formulations of uncertainty principle. In this talk we will be mostly focused on the discreet analog of uncertainty principle.