Branching random walks and searching in trees (10w5085)


Louigi Addario-Berry (McGill University)

(Inria Paris-Rocquencourt)

(McGill University)

(Oxford University)


The Banff International Research Station will host the "Branching random walks and searching in trees" workshop from January 31st to February 5th, 2010.

The use of tree-based data structures in algorithm design dates back to at least the 1940s. To this day, many of the fastest and easiest-to-implement algorithms have at their root a tree of one kind or another.
(In math lingo, a tree is an object that is "branching" and where, once branches diverge, they never meet again.)
The behavior of these data structures turns out to be intimately linked to the study of a probabilistic object known as a branching random walks. The purpose of this workshop is to explore the connections between branching random walks and tree-based data structures. Recent developments from both the probability and the theoretical computer science communities suggest that now may be the time to glean a deeper understanding of both the data structures commonly used in practice, and the probabilistic objects underlying them.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnologí­a (CONACYT).