Seminars

In this talk, we will continue, the proof of the Central Limit theorem from my last talk. We will show that that the law of "eigenregular" Gaussian polynomials is close to a Gaussian. The proof will be based on Stein's method and will be dependent...

In the last few years, there has been a lot of activity in the area of structural analysis and derandomization of polynomial threshold functions. Tools from analysis and probability have played a significant role in many of these works. The focus of...

A planar set that contains a unit segment in every direction is called a Kakeya set. These sets have been studied intensively in geometric measure theory and harmonic analysis since the work of Besicovich (1919); we find a new connection to game...

I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but have implications for quantum computing: 1...

How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a satisfactory answer is still elusive...

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a...

An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword. There is a fundamental...

The P != NP conjecture doesn't tell us what runtime is needed to solve NP-hard problems like 3-SAT and Hamiltonian Path. While some clever algorithms are known, they all require exponential time, and some researchers suspect that this is unavoidable...

There has been substantial progress on algorithmic versions and generalizations of the Lovasz Local Lemma recently, with some of the main ideas getting simplified as well. I will survey some of the main ideas of Moser & Tardos, Pegden, and David...

Byzantine agreement is a fundamental problem of distributed computing which involves coordination of players when a constant fraction are controlled by a malicious adversary. Each player starts with a bit, and the goal is for all good players to...