DIMACS Theory of Computing Seminar
Fall 2012

Place:                   CoRE 431
Time:                    Wednesdays 11:00 -- 12:00 Noon
Contacts:              Eric Allender    

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

TITLE (link to abstracts)
September 12
Amir Shpilka
On Sunflowers and Matrix Multiplication

September 19
Klim Efremenko
From Irreducible Representations to Locally Decodable Codes

September 26
Tim Roughgarden
Smoothness arguments and the price of anarchy

October 3
Arnab Bhattacharyya
Testing Assignments of Boolean CSPs

October 10
Anupam Gupta
How to Run your Chores, and Get to Dinner on Time
October 17
Eldar Fischer
Testing assignments for satisfying a read-once formula

October 24
Shubhangi Saraf
Rank bound for design matrices and applications to incidence theorems and locally correctable codes
(This is the day after FOCS.)
Seminar will be held in CORE 301(CORE A)
October 31
Akitoshi Kawamura
Distance k-sectors and zone diagrams
Canceled, due to Hurricane Sandy
November 7
Andrew Drucker
PCPs and hardness of approximation: beyond NP
November 14
Michal Koucky
Computing error-correcting codes by bounded-depth circuits
Seminar will be held in CORE 301(CORE A)
November 23

No seminar (Thanksgiving break)
November 28
David Cash
Efficient Authentication from the Learning Parity with Noise Problem
December 5
Ran Raz
The Surprise Examination Paradox and the Second Incompleteness Theorem