0
$\begingroup$

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 ?

Improve this question
$\endgroup$
1
  • $\begingroup$ It would be helpful if you identified the paper. $\endgroup$
    – chazisop
    May 17, 2012 at 16:59

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.