Paul Beame: Computing Elementary Statistics: Time-Space Tradeoffs and Sliding Windows

Speaker: Paul Beame , Professor, Dept. of Computer Science & Engineering, University of Washington

Date: Tuesday, October 28, 2014

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: G449 - Patil/Kiva

Event Type:

Room Description:

Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Paul Beame: Computing Elementary Statistics: Time-Space Tradeoffs and Sliding Windows

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.

All of these elementary statistics can be easily computed for sorted inputs; however, as Borodin and Cook showed more than 30 years ago, sorting with small space requires nearly quadratic time. Nearly tight time-space tradeoff lower bounds for comparison-based algorithms are known for these problems, including nearly quadratic lower bounds for element
distinctness and frequency moments, and it was conjectured that these bounds also hold for general algorithms.

Abstract: We give a new algorithm for element distinctness that beats the comparison-based lower bound by roughly an (n/S)^{1/2} factor and show how this tradeoff can be extended to sliding windows. A key component is an efficient generalization of Floyd's cycle-finding algorithm that can be applied for all space bounds. In contrast, we show that general algorithms for frequency moments do require quadratic tradeoffs over sliding windows.

We also give a tight time-space tradeoff lower bound for computing the median that generalizes lower bounds previously known only for comparison-based algorithms or for multi-pass data streams.

Joint work with Raphael Clifford, Widad Machmouchi, Vincent Liew, and Mihai Patrascu

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2014.

Created by Deborah Goodwin Email at Tuesday, October 21, 2014 at 11:03 AM.