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