Theoretical Computer Science
ds.algorithms lower-bounds survey data-streams streaming
Updated Fri, 03 Jun 2022 06:40:59 GMT

Functions and Counting Problems in Streaming Computation

I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08Paul Beame and Trinh Huynh. On the value of multiple read/write streams for approximating frequency moments). I am interested in this topic with design of algorithms and analysis of limitations.

I want a list of natural counting functions, which stream algorithm theorists often consider like NPcomplete problems list by Garey and Johnson .

Is there such a list ?


I don't know if there's a list of canonical hard problems, but there is a list of open problems in streaming as maintained by Andrew McGregor. This is not limited to the specific models you're referring to though.

External Links

External links referenced by this document: