Ven 04 décembre 2015 -- Erik Jan van Leeuwen (Max-Planck Institut für Informatik, Saarbrücken, Germany)

The Independent Set problem is a fundamental and well-studied graph problem, and asks to find a largest set of pairwise nonadjacent vertices of a graph. Although Independent Set is known to be NP-hard or worse for many graph classes, surprisingly, the complexity of Independent Set on graphs that exclude a ...

Ven 16 octobre 2015 -- Patrick Loiseau (EURECOM)

Statistical learning methods developed in the last decades have proved very useful for many applications. However, most algorithms were developed under the assumption that the data is independent from the algorithm. This is no longer true in applications where data is generated or provided by (human) strategic agents. As more ...