DIMACS Theory of Computing Seminar
Spring 2012

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

This seminar satisifes the "light seminar" (course 16:198:500:01, index number 69154) 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)
January 18
Ricky Rosen
A Strong Parallel Repetition Theorem for Projection Games on Expanders

January 25
Eric Allender
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

February 1
Mark Braverman
Towards Coding for Maximum Errors in Interactive Communication

February 8
Michael Saks
An optimal lower bound for file maintenance

February 15
Benny Pinkas
Secure Computation on the Web: Computing without Simultaneous Interaction

February 22
Yixin Xu
A Sharper Local Lemma with Improved Applications

February 29
Gagan Goel
Polyhedral Clinching Auctions and the AdWords Polytope

March 7
Aleksandar Nikolov
Optimal Private Halfspace Counting via Discrepancy

March 14

No seminar: Spring Break.
March 21
Jelani Nelson
Sparser Johnson-Lindenstrauss Transforms

March 28
Shubhangi Saraf
The Method of Multiplicities

April 4
Miguel Mosteiro
Opportunistic Information Dissemination in Mobile Ad-hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism

April 11
Bahman Kalantari
A Characterization Theorem and An Algorithm for A Convex Hull Problem

April 18
Aditya Bhaskara
Unconditionally Differentially Private Mechanisms for Linear Queries

April 25
Vinodchandran Variyam
On the Complexity of the Graph Reachability Problem

May 2
Vahab Mirrokni
Online Ad Allocation: Adversarial, Stochastic and Simultaneous Approximations

May 9
Donatella Firmani
Minimum Spanning Tree and Connectivity of Large Scale Graphs in MapReduce