Theory of Computation (TOC) Seminars

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

Subscribe to Theory of Computation (TOC) Seminars