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.
School of Mathematics
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.
I will discuss recent work on the global stability of the Euler-Maxwell equations in 3D (joint work with Guo and Pausader), and of the gravity water-wave system in 2D (joint work with Pusateri).
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.