DIMACS Theory of Computing Seminar
Fall 2011

Place:                   CoRE 431
Time:                    Wednesdays 11:00 -- 12:00 Noon
Contacts:              Michael Saks

This seminar satisifes the "light seminar" (course 16:198:500:01, index number 26617) requirement for the Department of Computer Science.     

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 7
Swastik Kopparty
The complexity of powering in finite fields

September 14
Rong Ge
Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach

September 21
Shachar Lovett
Existence of small families of t-wise independent permutations and t-designs via local limit theorems

September 28
Raghu Meka
Shorter long codes with applications to Unique Games

October 5
David Zuckerman
Privacy Amplification and Non-Malleable Extractors Via Character Sums

October 12
Ankur Moitra
Vertex Sparsification
Seminar will be held in CORE 301(CORE A)
October 19
Dana Ron
On sublinear algorithms for approximating graph parameters

October 26
Tony Wirth
Fast Adaptive Trees with Performance Bounds
Seminar will be held in CORE 301(CORE A)
November 2

Seminar canceled this week
November 9
Srikanth Srinivasan
Pseudorandom generators for read-once ACC^0_m
Seminar will be held in CORE 301(CORE A)
November 16
Graham Cormode
Mergeable Summaries

November 23

No seminar (Thanksgiving break)
November 30
Sergei Vassilvitskii
Dealing with Massive Data: Parallelism to the Rescue
Seminar will be held in CORE 301(CORE A)
December 7
Russell Impagliazzo
A Satisfiability Algorithm for $\AC^0$
Some small but important corrections.

Rescheduled from November 2 and the seminar will be held in CORE 301(CORE A)