Luc Devroye
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Luc Devroye has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Nicolas Fraiman
Department of Mathematics and Statistics, McGill University, Montreal, CanadaH3A 2K6
5 shared publications - Nicolas Broutin
School of Computer Science, McGill University, Montréal, Canada
4 shared publications - Erin McLeish
School of Computer Science, McGill University, Montréal, Canada
3 shared publications - Svante Janson
Department of Mathematics, Uppsala University, Uppsala, Sweden
3 shared publications - Gábor Lugosi
Department of Economics and Business Pompeu Fabra University Barcelona Spain
2 shared publications - Pat Morin
School of Computer Science, Carleton University, Ottawa, Canada
2 shared publications
Latest Publications
- 14 November 2019
- Published by Springer Nature in Algorithmica
- Vol. 82 (5) , 1329-1345
An Analysis of Budgeted Parallel Search on Conditional Galton–Watson Trees
- 14 November 2019
- Published by Springer Nature in Algorithmica
- Vol. 82 (5) , 1329-1345
An Analysis of Budgeted Parallel Search on Conditional Galton–Watson Trees
- 1 January 2018
- Published by Elsevier in Computational Geometry
- Vol. 67, 2-10
A note on interference in random networks
- 1 January 2018
- Published by Elsevier in Computational Geometry
- Vol. 67, 2-10
A note on interference in random networks
- 9 July 2014
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 23 (5) , 796-804
The Random Connection Model on the Torus
We study the diameter of a family of random graphs on the torus that can be used to model wireless networks. In the random connection model two pointsxandyare connected with probabilityg(y−x), wheregis a given function. We prove that the diameter of the graph is bounded by a constant, which depends only on ‖g‖1, with high probability as the number of vertices in the graph tends to infinity.
- 9 July 2014
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 23 (5) , 796-804
The Random Connection Model on the Torus
We study the diameter of a family of random graphs on the torus that can be used to model wireless networks. In the random connection model two pointsxandyare connected with probabilityg(y−x), wheregis a given function. We prove that the diameter of the graph is bounded by a constant, which depends only on ‖g‖1, with high probability as the number of vertices in the graph tends to infinity.
- Open Access
Protected nodes and fringe subtrees in some random trees
We study protected nodes in various classes of random rooted trees by putting them in the general context of fringe subtrees introduced by Aldous (1991). Several types of random trees are considered: simply generated trees (or conditioned Galton-Watson trees), which includes several cases treated separately by other authors, binary search trees and random recursive trees. This gives unified and simple proofs of several earlier results, as well as new results.
Open AccessProtected nodes and fringe subtrees in some random trees
We study protected nodes in various classes of random rooted trees by putting them in the general context of fringe subtrees introduced by Aldous (1991). Several types of random trees are considered: simply generated trees (or conditioned Galton-Watson trees), which includes several cases treated separately by other authors, binary search trees and random recursive trees. This gives unified and simple proofs of several earlier results, as well as new results.
- 26 February 2013
- Published by Wiley in Random Structures & Algorithms
- Vol. 45 (3) , 408-420
Connectivity of inhomogeneous random graphs
We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when . We draw n independent points Xi from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i, j) is added with probability , where is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 408‐420, 2014
- 26 February 2013
- Published by Wiley in Random Structures & Algorithms
- Vol. 45 (3) , 408-420
Connectivity of inhomogeneous random graphs
We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when . We draw n independent points Xi from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i, j) is added with probability , where is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 408‐420, 2014
- Open Access
Connectivity of inhomogeneous random graphs
We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when p = c log n/n. We draw n independent points X_i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i,j) is added with probability min(1, \K(X_i,X_j) log n/n), where \K \ge 0 is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined.
Open AccessConnectivity of inhomogeneous random graphs
We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when p = c log n/n. We draw n independent points X_i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i,j) is added with probability min(1, \K(X_i,X_j) log n/n), where \K \ge 0 is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined.
- 4 September 2012
- Published by Wiley in Random Structures & Algorithms
- Vol. 44 (1) , 45-66
Connectivity threshold of Bluetooth graphs
- 4 September 2012
- Published by Wiley in Random Structures & Algorithms
- Vol. 44 (1) , 45-66
Connectivity threshold of Bluetooth graphs
- 31 May 2012
- Published by Elsevier in Computational Geometry
- Vol. 45 (4) , 178-185
Memoryless routing in convex subdivisions: Random walks are optimal
- 31 May 2012
- Published by Elsevier in Computational Geometry
- Vol. 45 (4) , 178-185
Memoryless routing in convex subdivisions: Random walks are optimal
- 23 December 2011
- Published by Wiley in Random Structures & Algorithms
- Vol. 41 (1) , 66-98
Depth Properties of scaled attachment random recursive trees
We study depth properties of a general class of random recursive trees where each node i attaches to the random node \documentclass{article} \usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty} \begin{align*}\left\lfloor iX_i\right\rfloor\end{align*} and X0,…,Xn is a sequence of i.i.d. random variables taking values in [0,1). We call such trees scaled attachment random recursive trees (sarrt). We prove that the typical depth Dn, the maximum depth (or height) Hn and the minimum depth Mn of a sarrt are asymptotically given by Dn ∼μ‐1 log n, Hn ∼ αmax log n and Mn ∼ αmin log n where μ,αmax and αmin are constants depending only on the distribution of X0 whenever X0 has a density. In particular, this gives a new elementary proof for the height of uniform random recursive trees Hn ∼ elog n that does not use branching random walks.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011- 23 December 2011
- Published by Wiley in Random Structures & Algorithms
- Vol. 41 (1) , 66-98
Depth Properties of scaled attachment random recursive trees
We study depth properties of a general class of random recursive trees where each node i attaches to the random node \documentclass{article} \usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty} \begin{align*}\left\lfloor iX_i\right\rfloor\end{align*} and X0,…,Xn is a sequence of i.i.d. random variables taking values in [0,1). We call such trees scaled attachment random recursive trees (sarrt). We prove that the typical depth Dn, the maximum depth (or height) Hn and the minimum depth Mn of a sarrt are asymptotically given by Dn ∼μ‐1 log n, Hn ∼ αmax log n and Mn ∼ αmin log n where μ,αmax and αmin are constants depending only on the distribution of X0 whenever X0 has a density. In particular, this gives a new elementary proof for the height of uniform random recursive trees Hn ∼ elog n that does not use branching random walks.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011- Open Access
Sub-Gaussian tail bounds for the width and height of conditioned Galton--Watson trees
We study the height and width of a Galton--Watson tree with offspring distribution B satisfying E(B)=1, 0 < Var(B) < infinity, conditioned on having exactly n nodes. Under this conditioning, we derive sub-Gaussian tail bounds for both the width (largest number of nodes in any level) and height (greatest level containing a node); the bounds are optimal up to constant factors in the exponent. Under the same conditioning, we also derive essentially optimal upper tail bounds for the number of nodes at level k, for 1 <= k <= n.
Open AccessSub-Gaussian tail bounds for the width and height of conditioned Galton--Watson trees
We study the height and width of a Galton--Watson tree with offspring distribution B satisfying E(B)=1, 0 < Var(B) < infinity, conditioned on having exactly n nodes. Under this conditioning, we derive sub-Gaussian tail bounds for both the width (largest number of nodes in any level) and height (greatest level containing a node); the bounds are optimal up to constant factors in the exponent. Under the same conditioning, we also derive essentially optimal upper tail bounds for the number of nodes at level k, for 1 <= k <= n.