DIMACS/CS Light Seminar: Theoretical Computer Science
Spring 2011

Place:                   CoRE 431
Time:                   Wednesdays 11:00 -- 12:00 Noon
Contacts:               Michael Saks and Eric Allender and Mario Szegedy
Index number:     
198:500:02  (46133)

See also the schedule for the MATH and CS seminar series. Data on previous semesters is also available.
NOTE to external speakers: Please see dimacs webpage for directions.

TITLE (link to abstracts)
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