Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

23 mars 2020

TBA

Barnaby Martin (Durham)

TBA

9 mars 2020

TBA

Jean Marie Madiot (INRIA Paris)

TBA

24 février 2020

TBA

Alexis Bes (LACL - UPEC)

TBA

3 février 2020

Network Inference: Graph reconstruction and verification

Hang Zhou (LIX - Polytechnique)

How efficiently can we find an unknown graph using shortest path queries between its vertices? This is a natural theoretical question from the standpoint of recovery of hidden information. This question is related to discovering the topology of Internet networks, which is a crucial step for building accurate network models and designing efficient algorithms for Internet applications.

In this talk, I will introduce the problems of graph reconstruction and verification via oracles. I will investigate randomized algorithms based on a Voronoi cell decomposition. I will also analyze greedy algorithms, and prove that they are near-optimal.

The talk is based on joint work with Claire Mathieu and Sampath Kannan.

20 janvier 2020

TBA

Samuel Petite (LAMFA - Université de Picardie)

13 janvier 2020

TBA

Yann Strozecki (Laboratoire DAVID )

TBA