DATE
|
SPEAKER
|
TITLE
(link to
abstracts)
|
Notes
|
January 21
|
|
|
No Seminar This Week
|
January 28
|
Eric Allender
|
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds
|
|
February 4
|
Mark Braverman
|
Poly-logarithmic independence fools AC0 circuits
|
|
February 11
|
Pavel Hrubes
|
Arithmetic complexity of symmetric polynomials
|
|
February 18
|
Nikos Leonardos
|
Lower bounds on the randomized communication complexity
of read-once functions
|
|
February 25
|
Mohammad Hossein Bateni
|
Improved approximation algorithms for prize-collecting problems
|
|
March 4
|
|
Organizers are out of town
|
No Seminar This Week
|
March 11
|
Russell Impagliazzo
|
An Axiomatic Approach to Algebrization
|
|
March 18
|
|
Spring Break
|
No Seminar This Week
|
March 25
|
David Steurer
|
Message Passing Algorithms and Improved LP Decoding
|
CoRE 301
|
April 1
|
|
DIMACS Workshop on Property Testing
|
No Seminar; consider registering for the workshop
|
April 8
|
Qi Cheng
|
A Deterministic Reduction for the Gap Minimum Distance Problem
|
|
April 15
|
Virginia Vassilevska
|
Detecting, Finding and Minimizing Weighted Triangles
|
|
April 22
|
Ramamohan Paturi
|
On the Complexity of Circuit Satisfiability
|
CoRE 301
|
April 29
|
Peter Richter
|
On the hitting times of quantum versus random walks
|
CoRE 301
|
|