Projet RAP
Inria Paris-Rocquencourt
78153 Le Chesnay, France
tel: +33 1 39 63 56 88
fax: +33 1 39 63 55 96
email: firstname.name@inria.fr

I graduated in Computer Science from École Polytechnique (Paris) in 2001. Next I attended ENST Bretagne where I got a MSc in Mathematics and Cognitive Sciences (Cognitive Sciences Lab). I got a PhD in 2007 from McGill with a thesis written under the supervision of Luc Devroye. Between september 2007 and 2012, I have been a member of the Algorithms group at Inria. Since January 2009, I also participate to the course on Analysis of Algorithms at Master Parisien de Recherche en Informatique.

The Algorithms group lived happily until February 2011 when Philippe Flajolet, our fearless leader, tragically disappeared. We still do research and battle administration as he was doing feverishly, but it's just not the same without him. I joined the RAP team in September 2012.

For a picture of the beast, though not so recent, it's here.

[Research Interest]

I started by some applications to networks and gene multiplications and I now make my way towards more theoretical problems. Now looking towards probability applied to discrete structures and combinatorial geometry. Some precise current topics of research include mostly tree like structures:

  • analysis of algorihms and data structures
  • branching processes
  • random graphs
  • geometric networks
  • statistical physics

Also interested in percolation, mostly its finite applications. More about what I've done.

[Selected publications]
The scaling limit of the minimum spanning tree of a complete graph. L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont. Submitted (60 p), 2013. [aXv:1301.1664] [±]

Consider the minimum spanning tree of the complete graph with $n$ vertices, when edges are assigned independent random weights. We show that, when this tree is endowed with the graph distance renormalized by $n^{1/3}$ and with the uniform measure on its vertices, the resulting space converges in distribution as $n\to\infty$ to a random limiting metric space in the Gromov--Hausdorff--Prokhorov topology. We show that this space is a random binary $\mathbb R$-tree and has Minkowski dimension $3$ almost surely. In particular, its law is mutually singular with that of the Brownian continuum random tree or any rescaled version thereof. Our approach relies on a coupling between the minimum spanning tree problem and the Erdős--Rényi random graph, and the explicit description of its scaling limit in the so-called critical window.

The dual tree of a recursive triangulation of the disk. N. Broutin and H. Sulzbach. The Annals of Probability, vol. 43, pp. 738--781, 2015. [arXiv:1211.1343] [±]

In the recursive lamination of the disk, one tries to add chords one after another at random; a chord is kept and inserted if it does not intersect any of the previously inserted ones. Curien and Le Gall [Ann. Probab., vol. 39, pp. 2224--2270, 2011] have proved that the set of chords converges to a limit triangulation of the disk encoded by a continuous process $\mathscr M$. Based on a new approach resembling ideas from the so-called contraction method in function spaces, we prove that, when properly rescaled, the planar dual of the discrete lamination converges almost surely in the Gromov--Hausdorff sense to a limit real tree $\mathscr T$, which is encoded by $\mathscr M$. This confirms a conjecture of Curien and Le Gall.

Connectivity threshold for Bluetooth graphs. N. Broutin, L. Devroye, N. Fraiman, and G. Lugosi. Random Structures and Algorithms, vol. 44, pp. 45--66, 2014. [arXiv:1103.0351] [±]

We study the connectivity properties of random Bluetooth graphs that model certain ``ad hoc'' wireless networks. The graphs are obtained as ``irrigation subgraphs'' of the well-known random geometric graph model. There are two parameters that control the model: the radius $r$ that determines the ``visible neighbors'' of each node and the number of edges $c$ that each node is allowed to send to these. The randomness comes from the underlying distribution of data points in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters $r, c$ and completely characterize the connectivity threshold (in $c$) for values of $r$ close the critical value for connectivity in the underlying random geometric graph.

A limit process for partial match queries in random quadtrees and 2-d trees. N. Broutin, R. Neininger, and H. Sulzbach. The Annals of Applied Probability, vol. 23, pp. 2560--2603, 2013. [arXiv:1202.1342] [±]

We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the classical model where the data consist of independent and uniform points in the unit square. For this model, in a structure on $n$ points, it is known that the complexity, measured as the number of nodes $C_n(\xi)$ to visit in order to report the items matching a random query $\xi$, independent and uniformly distributed on $[0,1]$, satisfies $\mathbf E[C_n(\xi)]\sim \kappa n^{\beta}$, where $\kappa$ and $\beta$ are explicit constants. We develop an approach based on the analysis of the cost $C_n(s)$ of any fixed query $s\in [0,1]$, and give precise estimates for the variance and limit distribution. Moreover, a functional limit law for a rescaled version of the process $(C_n(s))_{0\le s\le 1}$ is derived in the space of cadlag functions with the Skorokhod topology. For the worst case complexity $\max_{s\in [0,1]} C_n(s)$ the order of the expectation as well as a limit law are given.

The continuum limit of critical random graphs. L. Addario-Berry, N. Broutin and C. Goldschmidt. Probability Theory and Related Fields, vol. 152, pp.367--406, 2012. [arXiv:0903.4730] [±]

We consider the Erdős-Rényi random graph $G(n,p)$ inside the critical window, that is when $p=1/n+\lambda n^{-4/3}$, for some fixed $\lambda\in \mathbb R$. We prove that the sequence of connected components of $G(n,p)$, considered as metric spaces using the graph distance rescaled by $n^{-1/3}$, converges towards a sequence of continuous compact metric spaces. The result relies on a bijection between graphs and certain marked random walks, and the theory of continuum random trees. Our result gives access to the answers to a great many questions about distances in critical random graphs. In particular, we deduce that the diameter of $G(n,p)$ rescaled by $n^{-1/3}$ converges in distribution to an absolutely continuous random variable with finite mean.

[Seminars in or around Paris]

Les probas du vendredi, Fridays at 11:00, UMPC, Jussieu.

Séminaire de Probabilités, Tuesdays at 16:30, LPMA, UPMC, Jussieu.

[Some Events]

Semester Disordered systems, random spatial processes and some applications IHP, Paris, Jan 5--Apr 3, 2015.

Winter School on Combinatorial and algorithmic aspects of convexity , IHP, Paris, Jan 19--23, 2015.

Workshop on spin glasses, random graphs and percolation IHP, Paris, Feb 16--20, 2015.

Journées ALEA CIRM, Luminy, Mar 16--20 2015.

Annual workshop on Probability, Combinatorics and Geometry McGill Bellair's Institute, Apr 3-10, 2015.

Combinatorial Probability: Conference in honour of Svante Janson's 60th birthday, Krusenberg, Sweden, June 1-5, 2015.

International meeting on probabilistic, combinatorial and asymptotic methods for the analysis of algorithms Strobl, Austria, Jun 8-12, 2015.

Cargèse fall school on random graphs Corsica, Sep 20-25, 2015.