Benjamin Rossman: The Average Sensitivity BoundedDepth Formulas Tuesday, October 13, 2015  4:15pm to 5:15pm Abstract: Hastad (1986) proved an exp( n^{1/d} ) lower bound on the size of depth d+1 (unbounded fanin) boolean *circuits* computing the PARITY function. 

Mika Göös: Communication Complexity vs. Partition Numbers Tuesday, October 6, 2015  4:15pm to 5:15pm ABSTRACT: 

Oded Regev: Faster algorithms for the Shortest Vector Problem Thursday, April 23, 2015  4:15pm to 5:15pm Abstract: We give a randomized ~2^ntime algorithm for solving the Shortest Vector Problem (SVP) on ndimensional lattices, improving on the previous best running time of 4^n by Micciancio and Voulgaris (STOC 2010). Despite being the fastest, the algorithm is arguably also the simplest in this 

Exponential Separation of Information and Communication Tuesday, December 2, 2014  4:15pm to 5:15pm Abstract: In profoundly influential works, Shannon and Huffman show that if Alice wants to send a message X to Bob, it's sufficient for her to send roughly H(X) bits (in expectation), where H denotes Shannon's entropy function. 

Tilting at Windmills: The Economic Efficiency of Large Games Tuesday, November 18, 2014  4:15pm to 5:15pm Abstract:


3SUM is Subquadratic Tuesday, November 4, 2014  4:15pm to 5:15pm Abstract: The 3SUM problem is to decide, given a set of N real numbers, whether any three of them sum to zero. A simple algorithm solves 3SUM in O(N^2) time and it has long been conjectured that this is the best possible. 

Computing Elementary Statistics: TimeSpace Tradeoffs and Sliding Windows Tuesday, October 28, 2014  4:15pm to 5:15pm Abstract: We consider the complexity of computing element distinctness, frequency moments, and order statistics with limited space, as well as computing these statistics over "sliding windows" in a single longer data sequence, a natural requirement for timeseries data. 

Zeev Dvir, Private Information Retrieval with 2Servers and subpolynomial communication Tuesday, October 7, 2014  4:15pm to 5:15pm 