Outils logiciels pour les cours Paris II

Cours Paris II

Stages/ Thèses

edit SideBar


  • 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,.....