Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete 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.

Analytical Approach to Parallel Repetition

Irit Dinur
Weizmann Institute; Radcliffe institute
April 15, 2013

We propose an “analytical” framework for studying parallel repetitions of one-round two-prover games. We define a new relaxation of the value of a game, val+, and prove that it is both multiplicative and a good approximation for the true value of the game. These two properties imply Raz's parallel repetition theorem as
$val(G^k) ~ val+(G^k) = val+(G)^k ~ val(G)^k$
Using this approach, we will describe a reasonably simple proof for the NP-hardness for $label-cover(1,delta)$, the starting point of many inapproximability results.