DIMACS/CS Light Seminar: Theoretical Computer Science
Fall 2010

Place:                   CoRE 431
Time:                   Wednesdays 11:00 -- 12:00 Noon
Contacts:               Michael Saks and Eric Allender
Index number:     
198:500:01  (07006)

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)
September 1

No Seminar This Week
September 8
Michael Saks

Approximating the longest increasing subsequence in polylogarithmic time
Seminar meets despite university schedule change
September 15
Swastik Kopparty
Random graphs and the parity quantifier

September 22
Leonid Levin
Arcane Information, Solving Relations, and Church Censorship

Seminar will be held in CORE 301
September 29
Alexandra Kolla
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers

October 6
Sergio de Biasi
Mollified Zone Diagrams and Their Computation

October 13
Ryan O'Donnell
Optimal lower bounds for locality sensitive hashing (except when q is tiny)

October 20
Kobbi Nissim
Approximately Optimal Mechanism Design via Differential Privacy

October 27

No Seminar This Week (FOCS)
November 3
Hoeteck Wee
Universal One-Way Hash Functions via Inaccessible Entropy

November 10
Russell Impagliazzo
Constructive Proofs of Concentration Bounds

November 17
Navin Goyal
Deterministic Algorithms for the Lovasz Local Lemma

Seminar will be held in CORE 301
November 24

No Seminar This Week
December 1
Kashyap Kolipaka
Moser and Tardos meet Lovasz

December 8
Bill Steiger
Six-way Equipartitioning by Three Lines Plus the Variance of Random Polygons