FOCS and Streams
Sounds like the name of a pub in Britain? Well, I came home after a long day and looked at the theory world in blogs, and saw the FOCS09 accepted list had been ripped apart into geometry, game theory and I am sure many others (eg learning, complexity, approximation) in peoples' minds. But there is a hanging chad and I will take it. People ask me whether streaming research is active. I am happy to point to (at least) three streaming-like papers in the list, so yes, it is active.
- Exact And Approximate Pattern Matching In The Streaming Model. Ely Porat and Benny Porat.
- The Data Stream Space Complexity of Cascaded Norms. T.S. Jayram and David Woodruff.
- Efficient sketches for Earth-Mover Distance, with applications. Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff.