<p>I don't know if there's a list of canonical hard problems, but there is a <a href="http://people.cs.umass.edu/~mcgregor/papers/11-openproblems.pdf" rel="nofollow">list of open problems in streaming</a> as maintained by Andrew McGregor. This is not limited to the specific models you're referring to  though. </p>

CC BY-SA 3.0
2012-05-18T02:39:50.753Z
2012-05-18T02:39:50.753Z
Suresh Venkat
<p>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 FOCS08（Paul 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.</p>

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

<p>Is there such a list ? </p>

CC BY-SA 3.0
2012-05-17T16:59:17.360Z
It would be helpful if you identified the paper.
chazisop
<ds.algorithms><lower-bounds><survey><data-streams><streaming>
Functions and Counting Problems in Streaming Computation
Jeigh
# Functions and Counting Problems in Streaming Computation

(Asked by: username_0 on 2012-05-17)

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 FOCS08（Paul 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 ?

**Tags:** ds.algorithms, lower-bounds, survey, data-streams, streaming
> **Comments:**
> **username_1**: It would be helpful if you identified the paper.  

---

## 1 answers

### Answer by username_2 on 2012-05-18. Score: 2 | Accepted answer

I don't know if there's a list of canonical hard problems, but there is a [list of open problems in streaming](http://people.cs.umass.edu/~mcgregor/papers/11-openproblems.pdf) as maintained by Andrew McGregor. This is not limited to the specific models you're referring to though.


---

