Luc Devroye

According to our database1, Luc Devroye authored at least 150 papers between 1976 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.



In proceedings 
PhD thesis 





Remote Sampling with Applications to General Entanglement Simulation.
Entropy, 2019

A lower bound on the size of an absorbing set in an arc-coloured tournament.
Discrete Mathematics, 2019

k -cuts on a Path.
Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

OMG: GW, CLT, CRT and CFTP (Flajolet Award Lecture).
Proceedings of the 29th International Conference on Probabilistic, 2018

The expected bit complexity of the von Neumann rejection algorithm.
Statistics and Computing, 2017

The graph structure of a deterministic automaton chosen at random.
Random Struct. Algorithms, 2017

Finding Adam in random growing trees.
Random Struct. Algorithms, 2017

Nonparametric estimation of a function from noiseless observations at random points.
J. Multivariate Analysis, 2017

On the measure of Voronoi cells.
J. Applied Probability, 2017

Exact Classical Simulation of the Quantum-Mechanical GHZ Distribution.
IEEE Trans. Information Theory, 2016

Random-Walk Perturbations for Online Combinatorial Optimization.
IEEE Trans. Information Theory, 2015

Random hyperplane search trees in high dimensions.
JoCG, 2015

Exceptional rotations of random graphs: a VC theory.
J. Mach. Learn. Res., 2015

On the Green's function of the partially diffusion-controlled reversible ABCD reaction for radiation chemistry codes.
J. Comput. Physics, 2015

The Analysis of Kademlia for Random IDs.
Internet Mathematics, 2015

Statistical Methods and Applications, 2014

On simulation and properties of the stable law.
Statistical Methods and Applications, 2014

Random variate generation for the generalized inverse Gaussian distribution.
Statistics and Computing, 2014

Connectivity of inhomogeneous random graphs.
Random Struct. Algorithms, 2014

Connectivity threshold of Bluetooth graphs.
Random Struct. Algorithms, 2014

Calculations of distance distributions and probabilities of binding by ligands between parallel plane membranes comprising receptors.
Computer Physics Communications, 2014

The Random Connection Model on the Torus.
Combinatorics, Probability & Computing, 2014

Exact Classical Simulation of the GHZ Distribution.
Proceedings of the 9th Conference on the Theory of Quantum Computation, 2014

Cellular Tree Classifiers.
Proceedings of the Algorithmic Learning Theory - 25th International Conference, 2014

Estimation of a Density Using Real and Artificial Data.
IEEE Trans. Information Theory, 2013

Transversals in Trees.
Journal of Graph Theory, 2013

Random sampling of the Green's Functions for reversible reactions with an intermediate state.
J. Comput. Physics, 2013

Connectivity for line-of-sight networks in higher dimensions.
Discrete Mathematics & Theoretical Computer Science, 2013

A Probabilistic Analysis of Kademlia Networks.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Prediction by random-walk perturbation.
Proceedings of the COLT 2013, 2013

Strong Universal Consistent Estimate of the Minimum Mean Squared Error.
Proceedings of the Empirical Inference - Festschrift in Honor of Vladimir N. Vapnik, 2013

Simulating Size-constrained Galton-Watson Trees.
SIAM J. Comput., 2012

Depth Properties of scaled attachment random recursive trees.
Random Struct. Algorithms, 2012

An affine invariant k-nearest neighbor regression estimate.
J. Multivariate Analysis, 2012

Memoryless routing in convex subdivisions: Random walks are optimal.
Comput. Geom., 2012

An affine invariant k-nearest neighbor regression estimate.
Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

A Note on Interference in Random Networks.
Proceedings of the 24th Canadian Conference on Computational Geometry, 2012

The double CFTP method.
ACM Trans. Model. Comput. Simul., 2011

Distances between pairs of vertices and vertical profile in conditioned Galton-Watson trees.
Random Struct. Algorithms, 2011

Almost all Delaunay triangulations have stretch factor greater than pi/2.
Comput. Geom., 2011

On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification.
J. Multivariate Analysis, 2010

Note on the Structure of Kruskal's Algorithm.
Algorithmica, 2010

Classification and Trees.
Proceedings of the Structural, 2010

Random variate generation for exponentially and polynomially tilted stable distributions.
ACM Trans. Model. Comput. Simul., 2009

Random Hyperplane Search Trees.
SIAM J. Comput., 2009

On the k-orientability of random graphs.
Discrete Mathematics, 2009

The spanning ratio of the Delaunay triangulation is greater than pi/2.
Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

On the Performance of Clustering in Hilbert Spaces.
IEEE Trans. Information Theory, 2008

The height of increasing trees.
Random Struct. Algorithms, 2008

Consistency of Random Forests and Other Averaging Classifiers.
J. Mach. Learn. Res., 2008

An Analysis of the Height of Tries with Random Weights on the Edges.
Combinatorics, Probability & Computing, 2008

Weighted height of random trees.
Acta Inf., 2008

On the stabbing number of a random Delaunay triangulation.
Comput. Geom., 2007

Multiple choice tries and distributed hash tables.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Large Deviations for the Weighted Height of an Extended Class of Trees.
Algorithmica, 2006

Random Multivariate Search Trees.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

Two-Way Chaining with Reassignment.
SIAM J. Comput., 2005

Probabilistic behavior of asymmetric level compressed tries.
Random Struct. Algorithms, 2005

Maxima in hypercubes.
Random Struct. Algorithms, 2005

Universal Asymptotics for Random Tries and PATRICIA Trees.
Algorithmica, 2005

A note on density model size testing.
IEEE Trans. Information Theory, 2004

Distances and Finger Search in Random Binary Search Trees.
SIAM J. Comput., 2004

On Worst-Case Robin Hood Hashing.
SIAM J. Comput., 2004

Expected worst-case partial match in random quadtries.
Discrete Applied Mathematics, 2004

Expected time analysis for Delaunay point location.
Comput. Geom., 2004

Random suffix search trees.
Random Struct. Algorithms, 2003

Cuckoo hashing: Further analysis.
Inf. Process. Lett., 2003

A note on robust hypothesis testing.
IEEE Trans. Information Theory, 2002

Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees.
SIAM J. Comput., 2002

On the Spanning Ratio of Gabriel Graphs and beta-skeletons.
Proceedings of the LATIN 2002: Theoretical Informatics, 2002

Succinct Data Structures for Approximating Convex Functions with Applications.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2002

Random Tries.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

Paul Erdös memorial lecture.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

Analysis of random LC tries.
Random Struct. Algorithms, 2001

On the Probablistic Worst-Case Time of "Find".
Algorithmica, 2001

Analysis of range search for random k-d trees.
Acta Inf., 2001

Squarish k-d Trees.
SIAM J. Comput., 2000

Estimating the number of vertices of a polyhedron.
Inf. Process. Lett., 2000

The Height and Size of Random Hash Trees and Random Pebbled Hash Trees.
SIAM J. Comput., 1999

On the complexity of branch-and-bound search for random trees.
Random Struct. Algorithms, 1999

Lower Bounds for Bayes Error Estimation.
IEEE Trans. Pattern Anal. Mach. Intell., 1999

Properties of Random Triangulations and Trees.
Discrete & Computational Geometry, 1999

A Note on the Expected Time for Finding Maxima by List Algorithms.
Algorithmica, 1999

Fast delaunay point location with search structures.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

Universal Limit Laws for Depths in Random Trees.
SIAM J. Comput., 1998

Unoriented Theta-Maxima in the Plane: Complexity and Algorithms.
SIAM J. Comput., 1998

A study of random Weyl trees.
Random Struct. Algorithms, 1998

On the Richness of the Collection of Subtrees in Random Binary Search Trees.
Inf. Process. Lett., 1998

Intersections with random geometric objects.
Comput. Geom., 1998

A Note on Point Location in Delaunay Triangulations of Random Points.
Algorithmica, 1998

Random Variate Generation for Multivariate Unimodal Densities.
ACM Trans. Model. Comput. Simul., 1997

On the Horton-Strahler Number for Random Tries.
ITA, 1996

Random Variate Generation in One Line of Code.
Proceedings of the 28th conference on Winter simulation, 1996

Diamonds Are Not a Minimum Weight Triangulation's Best Friend.
Proceedings of the 8th Canadian Conference on Computational Geometry, 1996

On the Variance of the Height of Random Binary Search Trees.
SIAM J. Comput., 1995

On the Generation of Random Binary Search Trees.
SIAM J. Comput., 1995

The Strong Convergence of Maximal Degrees in Uniform Random Recursive Trees and Dags.
Random Struct. Algorithms, 1995

Lower bounds in pattern recognition and learning.
Pattern Recognition, 1995

A Note on the Horton-Strahler Number for Random Trees.
Inf. Process. Lett., 1995

The Botanical Beauty of Random Binary Trees.
Proceedings of the Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, 1995

On Random Cartesian Trees.
Random Struct. Algorithms, 1994

A Note on the Horton-Strahler Number for Random Trees.
Inf. Process. Lett., 1994

Intersections of random line segments.
Int. J. Comput. Geometry Appl., 1994

Convex Hulls for Random Lines.
J. Algorithms, 1993

On the Expected Height of Fringe-Balanced Trees.
Acta Inf., 1993

A Note on the Height of Suffix Trees.
SIAM J. Comput., 1992

A Note on the Probabilistic Analysis of Patricia Trees.
Random Struct. Algorithms, 1992

Generation of random objects.
Proceedings of the 24th Winter Simulation Conference, 1992

Algorithms for Generating Discrete Random Variables with a Given Generating Function or a Given Moment Sequence.
SIAM J. Scientific Computing, 1991

Limit Laws for Local Counters in Random Binary Search Tree.
Random Struct. Algorithms, 1991

Expected time analysis of a simple recursive Poisson random variate generator.
Computing, 1991

An Analysis of Random d-Dimensional Quad Trees.
SIAM J. Comput., 1990

On the Height of Random m-ary Search Trees.
Random Struct. Algorithms, 1990

Coupled Samples in Simulation.
Operations Research, 1990

On Global Costs and Nyquist's Theorem in Random Variate Generation.
Math. Oper. Res., 1989

Probabilistic Analysis of Algorithms and Data Structures.
Proceedings of the Algorithms and Data Structures, 1989

Automatic Pattern Recognition: A Study of the Probability of Error.
IEEE Trans. Pattern Anal. Mach. Intell., 1988

Applications of the Theory of Records in the Study of Random Trees.
Acta Inf., 1988

Generating sums in constant average time.
Proceedings of the 20th conference on Winter simulation, 1988

A simple generator for discrete log-concave distributions.
Computing, 1987

Branching Processes in the Analysis of the Heights of Trees.
Acta Inf., 1987

A note on the height of binary search trees.
J. ACM, 1986

Grid methods in simulation and random variate generation.
Computing, 1986

Sample-based non-uniform random variate generation.
Proceedings of the 18th conference on Winter simulation, WSC 1986, 1986

Data Structures in Kernel Density Estimation.
IEEE Trans. Pattern Anal. Mach. Intell., 1985

The Expected Length of the Longest Probe Sequence for Bucket Searching when the Distribution is Not Uniform.
J. Algorithms, 1985

A Note on the Expected Time Required to Construct the Outer Layer.
Inf. Process. Lett., 1985

Exponential Bounds for the Running Time of a Selection Algorithm.
J. Comput. Syst. Sci., 1984

A simple algorithm for generating random variates with a log-concave density.
Computing, 1984

Random variate generation for unimodal and monotone densities.
Computing, 1984

A Probabilistic Analysis of the Height of Tries and of the Complexity of Triesort.
Acta Inf., 1984

Moment inequalities for random variables in computational geometry.
Computing, 1983

Linear Sorting with O(log n) Processors.
BIT, 1983

Any Discrimination Rule Can Have an Arbitrarily Bad Probability of Error for Finite Sample Size.
IEEE Trans. Pattern Anal. Mach. Intell., 1982

A note on the average depth of tries.
Computing, 1982

On the Inequality of Cover and Hart in Nearest Neighbor Discrimination.
IEEE Trans. Pattern Anal. Mach. Intell., 1981

A note on linear expected time algorithms for finding convex hulls.
Computing, 1981

Average time behavior of distributive sorting algorithms.
Computing, 1981

The computer generation of poisson random variables.
Computing, 1981

Recent results in non-uniform random variate generation.
Proceedings of the 13th conference on Winter simulation, 1981

A Note on Finding Convex Hulls Via Maximal Vectors.
Inf. Process. Lett., 1980

Distribution-free performance bounds for potential function rules.
IEEE Trans. Information Theory, 1979

Distribution-free performance bounds with the resubstitution error estimate (Corresp.).
IEEE Trans. Information Theory, 1979

Distribution-free inequalities for the deleted and holdout error estimates.
IEEE Trans. Information Theory, 1979

Inequalities for the Completion Times of Stochastic PERT Networks.
Math. Oper. Res., 1979

The uniform convergence of nearest neighbor regression function estimators and their application in optimization.
IEEE Trans. Information Theory, 1978

Progressive global random search of continuous functions.
Math. Program., 1978

Probabilistic Search as a Strategy Selection Procedure.
IEEE Trans. Systems, Man, and Cybernetics, 1976

On the Convergence of Statistical Search.
IEEE Trans. Systems, Man, and Cybernetics, 1976

A distribution-free performance bound in error estimation (Corresp.).
IEEE Trans. Information Theory, 1976