The broadcasting problem

schedule le lundi 23 novembre 2020 de 17h00 à 18h00

Organisé par : E. Bodiot, L. Broux, T. Randrianarisoa, G. Buriticá, Y. Tardy

Intervenant : Vasiliki Velona (Universitat Pompeu Fabra and Universitat Politècnica de Catalunya / Visiting LPSM)
Lieu : Online at Zoom:

Sujet : The broadcasting problem

Résumé :

Consider a large rooted tree, where the root-vertex of the tree has a random bit value assigned. Every other vertex has the same bit value as its parent with probability 1-q and the opposite value with probability q, where q\in [0,1]. The broadcasting problem consists in estimating the value of the root bit, upon observing the unlabelled tree graph and the bit values associated with a subset of the vertices. I will discuss such results on various tree classes and, in particular, on random recursive trees created either by the uniform attachment model or by the linear preferential attachment model.