Theory of Computation (TOC) Seminars

Robin Kothari: Separations in Query Complexity Using Cheat Sheets
Tuesday, November 17, 2015 - 4:00pm to 5:00pm

Abstract: 2015 has been an exciting year for query complexity. I'll survey some of the breakthroughs ​made this year and then talk about some very recent work with my collaborators Scott Aaronson and Shalev Ben-David.​

Virginia Vassilevska Williams: Fine-Grained Algorithms and Complexity
Tuesday, November 10, 2015 - 4:00pm to 5:00pm
Benjamin Rossman: The Average Sensitivity Bounded-Depth 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 fan-in) boolean *circuits* computing the PARITY function.
Mika Göös: Communication Complexity vs. Partition Numbers
Tuesday, October 6, 2015 - 4:15pm to 5:15pm


Oded Regev: Faster algorithms for the Shortest Vector Problem
Thursday, April 23, 2015 - 4:15pm to 5:15pm

Abstract:  We give a randomized ~2^n-time algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional 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
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: Time-Space 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 time-series data.
Zeev Dvir, Private Information Retrieval with 2-Servers and sub-polynomial communication
Tuesday, October 7, 2014 - 4:15pm to 5:15pm


Subscribe to Theory of Computation (TOC) Seminars