Theory of Computation (TOC) Seminars
 |
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 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^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 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: 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 |
Pages
