DATE
|
SPEAKER
|
TITLE
(link to
abstracts)
|
Notes
|
January 19
|
Luke Friedman
|
Limits on the Computational Power of Random Strings
|
|
January 26
|
Paul Beame
|
Making Branching Programs Oblivious Requires Superlogarithmic Overhead
|
|
February 2
|
|
|
No Seminar This Week (But note talks this week by Saraf, Sherstov, and Cash)
|
February 9
|
Nikhil Srivastava
|
An Elementary Proof of the Restricted Invertibility Theorem
|
|
February 16
|
Madhur Tulsiani
|
Reductions Between Expansion Problems
|
|
February 23
|
Shachar Lovett
|
Linear Systems Over Finite Abelian Groups
|
|
March 2
|
|
|
No Seminar This Week (Organizers Out of Town)
|
March 9
|
Ofer Neiman
|
Near Linear Lower Bound for Dimension Reduction in L_1
|
|
March 16
|
|
|
No Seminar This Week (Spring Break)
|
March 23
|
Grant Schoenebeck
|
Understanding the Limitations of Linear and Semidefinite Programming
|
|
March 30
|
Sanjeev Khanna
|
Perfect Matchings in Regular Bipartite Graphs
|
|
April 6
|
Ashwin Nayak
|
Recognizing well-parenthesized expressions in the streaming model
|
|
April 13
|
Srikanth Srinivasan
|
The Hardness of the Noncommutative Determinant
|
|
April 20
|
Rocco Servedio
|
Learning and testing k-modal distributions
|
|
April 27
|
Dmitry Gavinsky
|
Quantum Fingerprints that Keep Secrets
|
|
|