Probabilistic analysis of optimal multi-pivot Quicksort.
Submitted for publication (2025)
[PDF]
On fine fluctuations of the complexity of the QuickSelect algorithm.
Submitted for publication (2024)
[PDF]
On Policy Evaluation Algorithms in Distributional Reinforcement Learning.
Submitted for publication (2024)
[PDF]
Random 2-SAT: The set of atoms of the limiting empirical marginal distribution.
Annales de l'Institut Henri Poincaré D: Combinatorics, Physics and their Interactions, accepted for publication (2026)
[PDF]
A distributional analysis of QuickXsort for Mergesort.
37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026), Art. No. 22, 14 pp, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2026.
[ARTICLE] [PDF]
The analysis of partial match queries in random multidimensional trees: A selected survey
Computer Science Review, 61 (2026), 100904.
[ARTICLE] [PDF]
Bivariate change point detection in movement direction and speed.
Electronic Journal of Statistics, 19 (2025), 2121-2170.
[ARTICLE] [PDF]
Patricia's Bad Distributions.
35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA24), Art. No. 25, 8 pp, Leibniz Int. Proc. Inform., 302, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024.
[ARTICLE] [PDF]
On fluctuations of complexity measures for the FIND algorithm.
35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA24), Art. No. 9, 15 pp, Leibniz Int. Proc. Inform., 302, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024.
[ARTICLE] [PDF]
On solutions of the distributional Bellman equation.
Electron. Res. Arch., 31 (2023), 4459-4483. Special Issue: Mathematics of Machine Learning and Related Topics.
[ARTICLE] [PDF]
On the contraction method with reduced independence assumptions.
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA22), (2022), 14:1-14:13.
[ARTICLE] [PDF]
A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees.
Discrete Applied Mathematics, 292 (2021), 64-71.
[ARTICLE] [PDF]
Node profiles of symmetric digital search trees: Concentration properties
Random Structures and Algorithms, 58 (2021), no. 3, 430-467.
[ARTICLE] [PDF]
Convergence Rates in the Probabilistic Analysis of Algorithms.
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), (2020), 22:1-22:13.
[ARTICLE] [PDF]
Process convergence for the complexity of Radix Selection on Markov sources.
Stochastic Processes and their Applications, 129 (2019), 507-538.
[ARTICLE] [PDF]
Refined Asymptotics for the Composition of Cyclic Urns.
Electronic Journal of Probability, 23 (2018), no. 117, 1-20.
![[ARTICLE]](art.gif)
[PDF]
Probabilistic Analysis of the Dual-Pivot Quicksort "Count".
Analytic Algorithmics and Combinatorics (ANALCO) (2018), 1-7.
[PDF]
External Profile of Symmetric Digital Search Trees (Extended Abstract).
Analytic Algorithmics and Combinatorics (ANALCO) (2017), 124-130.
[PDF]
Rates of convergence for balanced irreducible two-color Pólya urns.
Analytic Algorithmics and Combinatorics (ANALCO) (2017), 94-99.
[PDF]
Dependence and phase changes in random m-ary search trees.
Random Structures and Algorithms, 50 (2017), no. 3, 353–379.
[PDF]
A Limit Theorem for Radix Sort and Tries with Markovian Input.
Submitted for publication.
[PDF]
The CLT Analogue for Cyclic Urns.
Analytic Algorithmics and Combinatorics (ANALCO) (2016), 121-127.
[PDF]
On a functional contraction method.
The Annals of Probability, 43 (2015), 1777-1822.
[PDF]
Average Case and Distributional Analysis of Dual Pivot Quicksort.
ACM Transactions on Algorithms, 11 (2015), Article No. 22.
[PDF]
Refined Quicksort asymptotics.
Random Structures and Algorithms, 46 (2015), 346-361.
[PDF]
A multiple filter test for the detection of rate changes in renewal processes with varying variance.
The Annals of Applied Statistics, 8 (2014), 2027-2067.
[PDF]
Analysis of radix selection on Markov sources.
Proceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms.
(Eds. M. Bousquet-Mélou, M. Soria). DMTCS-HAL Proceedings series (2014), 253-264.
[PDF]
Pólya Urns Via the Contraction Method.
Combinatorics, Probability & Computing, 23 (2014), 1148-1186.
[ARTICLE] [PDF] © Cambridge University Press
A Gaussian limit process for optimal FIND algorithms.
Electronic Journal of Probability, 19 (2014), no. 3, 1-28.
[ARTICLE] [PDF]
A statistical view on exchanges in Quickselect.
Analytic Algorithmics and Combinatorics (ANALCO) (2014), 40-51.
[PDF]
A limit process for partial match queries in random quad trees and 2-d trees.
The Annals of Applied Probability, 23 (2013), 2560-2603.
[ARTICLE] [PDF]
Appendix to "Approximating perpetuities".
Methodology and Computing in Applied Probability, 15 (2013), 707-712.
[ARTICLE] [PDF]
Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model.
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) (2013), 877-886.
[ARTICLE] [PDF]
Asymptotic analysis of Hoppe trees.
Journal of Applied Probability, 50 (2013), 228-238.
[ARTICLE] [PDF]
Partial match queries in random quadtrees.
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) (2012), 1056-1065,
[ARTICLE] [PDF]
Approximating perpetuities.
Methodology and Computing in Applied Probability, 10 (2008), 507-529.
[ARTICLE] [PDF]
The size of random fragmentation trees.
Probability Theory and Related Fields, 142 (2008), 399-442.
[ARTICLE] [PS] [PDF]
A functional limit theorem for the profile of search trees.
The Annals of Applied Probability 18 (2008), 288-333.
[ARTICLE] [PDF]
Tail bounds for the Wiener index of random trees.
DMTCS Proceedings (2007 Conference on Analysis of Algorithms), (2007), 279-290.
[ARTICLE] [PS] [PDF]
A note on the approximation of perpetuities.
DMTCS Proceedings (2007 Conference on Analysis of Algorithms), (2007), 115-126.
[ARTICLE] [PS] [PDF]
On the Length Distribution of External Branches in Coalescence Trees: Genetic Diversity within Species.
Theoretical Population Biology, 72 (2007), 245-252.
[ARTICLE] [PDF]
Profiles of random trees: Limit theorems for random recursive trees and binary search trees.
Algorithmica 46 (2006), 367-407.
[ARTICLE] [PDF]
A survey of multivariate aspects of the contraction method.
Discrete Mathematics & Theoretical Computer Science 8 (2006), 31-56.
[ARTICLE] [PS] [PDF]
A limit law for the root value of minimax trees.
Electronic Communications in Probability 10 (2005), 273-281.
[ARTICLE] [PDF]
Recursive random variables with subgaussian distributions.
Statistics & Decisions, 23 (2005), no. 2, 131-146.
[ARTICLE] [PDF] ©
Analysis of algorithms by the contraction method: additive and max-recursive sequences.
Interacting Stochastic Systems, 435-450, Springer, 2005.
[ARTICLE] [PS] [PDF]
Stochastische Analyse von Algorithmen, Fixpunktgleichungen und ideale Metriken.
Habilitation (kumulativ), Universität Frankfurt a. M., 45 p. (2004).
[PDF]
Probabilistic analysis for randomized game tree evaluation.
Mathematics and Computer Science III (Vienna 2004), 163-174,
Trends in Mathematics, Birkhäuser, Basel, 2004.
[ARTICLE] [PS] [PDF]
On the contraction method with degenerate limit equation.
The Annals of Probability 32 (2004), no. 3B, 2838-2856.
[ARTICLE] [PDF] ©
Distances and finger search in random binary search trees.
SIAM Journal on Computing 33 (2004), no. 3, 647-658.
[ARTICLE] [PS] [PDF]
A general limit theorem for recursive algorithms and combinatorial structures.
The Annals of Applied Probability 14 (2004), no. 1, 378-418.
[ARTICLE] [PDF] ©
Random suffix search trees.
Random Structures and Algorithms, 23 (2003), no. 4, 357-396.
[ARTICLE] [PS] [PDF]
Distribution of distances in random binary search trees.
The Annals of Applied Probability 13 (2003), no. 1, 253 -276.
[ARTICLE] [PDF] ©
The Wiener index of random trees.
Combinatorics, Probability & Computing 11 (2002), no. 6, 587-597.
[ARTICLE] [PS] [PDF]
A note on random suffix search trees.
Mathematics and Computer Science II (Versailles 2002), 267-278,
Trends in Mathematics, Birkhäuser, Basel, 2002.
[ARTICLE] [PS] [PDF]
Rates of convergence for quicksort.
Journal of Algorithms 44 (2002), no. 1, 52-62.
[ARTICLE] [PS] [PDF]
Phase change of limit laws in the quicksort recurrence under varying toll functions.
SIAM Journal on Computing 31 (2002), no. 6, 1687-1722.
[ARTICLE] [PS] [PDF]
Density approximation and exact simulation of random variables that are solutions of fixed-point equations.
Advances in Applied Probability 34 (2002), no. 2, 441-468.
[ARTICLE] [PS] [PDF]
On binary search tree recursions with monomials as toll functions.
Journal of Computational and Applied Mathematics 142 (2002), no. 1, 185-196.
[ARTICLE] [PS] [PDF]
On a multivariate contraction method for random recursive structures with applications to quicksort.
Random Structures and Algorithms 19 (2001), no. 3-4, 498-524.
[ARTICLE] [PS] [PDF]
Rates of convergence for products of random stochastic 2x2 matrices.
Journal of Applied Probability 38 (2001), no. 3, 799-806.
[ARTICLE] [PS] [PDF]
Limit laws for partial match queries in quadtrees.
The Annals of Applied Probability 11 (2001), no. 2, 452-469.
[ARTICLE] [PDF] ©
Asymptotic distributions for partial match queries in K-d trees.
Random Structures and Algorithms 17 (2000), no. 3-4, 403-427.
[ARTICLE]
Perfect simulation from the quicksort limit distribution.
Electronic Communications in Probability 5 (2000), 95-99 (electronic).
[ARTICLE] [PDF]
On the internal path length of d-dimensional quad trees.
Random Structures and Algorithms 15 (1999), no. 1, 25-41.
[ARTICLE]
Limit Laws for Random Recursive Structures and Algorithms.
Dissertation, Universität Freiburg i. Br., iv, 96 p. (1999).
[PS] [PDF]