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...