# On monday, at 2pm - UPEC CMC - Room P2-131

### April 6, 2020

*Vacances scolaires*

### March 23, 2020

*TBA*

**Barnaby Martin**

TBA

### March 9, 2020

*TBA*

**Jean Marie Madiot**

TBA

### February 24, 2020

*TBA*

**Alexis Bes**

TBA

### February 17, 2020

*Vacances scolaires*

### February 10, 2020

*Vacances scolaires*

### February 3, 2020

*Network Inference: Graph reconstruction and verification*

**Hang Zhou**

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.

### January 27, 2020

*Controlling a random population*

**Pierre Ohlmann**

Bertrand et al. (2017) introduced a model of parameterised

systems, where each agent is represented by a finite state system, and

studied the following control problem: for any number of agents, does

there exist a controller able to bring all agents to a target state? They

showed that the problem is decidable and EXPTIME-complete in the

adversarial setting, and posed as an open problem the stochastic setting,

where the agent is represented by a Markov decision process. In this

paper, we show that the stochastic control problem is decidable. Our

solution makes significant uses of well quasi orders, of the max-flow min-

cut theorem, and of the theory of regular cost functions.

### January 20, 2020

*TBA*

**Samuel Petite**