The PI's research includes the use of fixed-point methods, the method of moments, and complex-analytic singularity analysis to study additive functionals on random trees, which arise in the analysis of divide-and-conquer algorithms. It seeks to explain, using continuum random trees and Brownian excursion or otherwise, an invariance of distributions observed across various random-trees models. A refined analysis, under the so-called random permutation model, of the periodic asymptotic distributional behavior of additive functionals for trees with large branching factor also extends to urn models and multi-type branching processes. Additionally, the research encompasses digital analyses and improvements of algorithms for searching and sorting, such as the widely-used Quicksort; use of a perfect simulation algorithm pioneered by the PI to estimate mixing times of Markov chains statistically; and the novel application of Mellin transforms to the study of small deviations (small-ball probabilities) for Gaussian random fields.
The research to be performed lies at the interface of probability and computer science. It involves the design and application of efficient algorithms for computer simulation from complicated probability distributions; the probabilistic analysis of algorithms and data structures arising in connection with such basic and important algorithms as Quicksort, which is the standard sorting procedure in Unix systems and which, in a computer science review paper in 2000, was cited as one of the ten algorithms with the greatest influence on the development and practice of science and engineering in the last century; and the novel application of a common analysis-of-algorithms tool ("Mellin transforms") to an area of probability ("small deviations", involving the estimation of the chance of certain uncommon events).
