Seminars

May
13
2014

Computer Science/Discrete Mathematics Seminar II

A central limit theorem for Gaussian polynomials and deterministic approximate counting for polynomial threshold functions
10:30am|West Bldg. Lect. Hall
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...
Apr
29
2014

Computer Science/Discrete Mathematics Seminar II

A central limit theorem for Gaussian polynomials and deterministic approximate counting for polynomial threshold functions
10:30am|S-101
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...
Apr
28
2014

Computer Science/Discrete Mathematics Seminar I

Search games and Optimal Kakeya Sets
Yuval Peres
11:15am|S-101

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

Apr
22
2014

Computer Science/Discrete Mathematics Seminar II

Results and open problems in theory of quantum complexity
10:30am|S-101
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...
Apr
21
2014

Computer Science/Discrete Mathematics Seminar I

True Randomness: Its Origin and Expansion
Yaoyun Shi
11:15am|S-101

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

Apr
15
2014

Computer Science/Discrete Mathematics Seminar II

IP = PSPACE via error correcting codes
10:30am|S-101
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...
Apr
14
2014

Computer Science/Discrete Mathematics Seminar I

Local Correctability of Expander Codes
Brett Hemenway
11:15am|S-101

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

Apr
08
2014

Computer Science/Discrete Mathematics Seminar II

Do NP-Hard Problems Require Exponential Time?
10:30am|S-101

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

Apr
07
2014

Computer Science/Discrete Mathematics Seminar I

Progress on algorithmic versions of the Lovasz Local Lemma
11:15am|S-101

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

Apr
01
2014

Computer Science/Discrete Mathematics Seminar II

Byzantine Agreement in Expected Polynomial Time
10:30am|West Bldg. Lect. Hall

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