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