Stages

Streaming algorithms are efficient algorithms on streams, using a sublinear space. For example, a stream of edges defines dynamic graphs for which we study graph properties. There are many lower bounds techniques which for general graph problems show a linear lower bound on worst-case data.
An interesting new area is to concentrate on streams of edges which follow a statistical law, for example a power law degree distribution. Do the lower bounds still hold?
Examples: Spanning trees, Diameter, matchings,.....

UP2