Archeology of Random Trees
Part of the Special ECE Seminar Series
Modern Artificial Intelligence
Title:
Archeology of random trees
Speaker:
Gabor Lugosi, ICREA research professor at the Department of Economics, Pompeu Fabra University
Abstract:
Networks are often naturally modeled by random processes in which nodes of the network are added one-by-one, according to some random rule. Uniform and preferential attachment trees are among the simplest examples of such dynamically growing networks. The statistical problems we address in this talk regard discovering the past of the tree when a present-day snapshot is observed. We present a few results that show that, even in gigantic networks, a lot of information is preserved from the very early days. In particular, we discuss the problem of finding the root and the broadcasting problem.
Bio:
Gabor Lugosi is an ICREA research professor at the Department of Economics, Pompeu Fabra University, Barcelona. He graduated in electrical engineering at the Technical University of Budapest in 1987, and received his Ph.D. from the Hungarian Academy of Sciences in 1991. His main research interests include the theory of machine learning, combinatorial statistics, and information theory.