JournalsowrVol. 8 / No. 2DOI 10.4171/owr/2011/23

Mini-Workshop: Random Trees, Information and Algorithms

  • Ralph Neininger

    J. W. Goethe-Universität, Frankfurt, Germany
  • Wojciech Szpanowski

    Purdue University, West Lafayette, USA
Mini-Workshop: Random Trees, Information and Algorithms cover

You need to subscribe to download the article.

Abstract

The subject of this Mini-Workshop is the probabilistic analysis of random tree models that originate from applications in Computer Science. Emphasis is put on their connections to algorithms and information theory. Trees with a stochastic growth dynamic appear in Computer Science as data structures, in the context of coding schemes as well as connected to fundamental algorithms such as sorting, searching and selecting. The focus of this Mini-Workshop is on probabilistic and analytic techniques that have been developed recently in the asymptotic analysis of random trees such as martingale methods, connections to branching random walks, the contraction method, the method of moments as well as various techniques based on generating functions.