Yury Poyansky (MIT)

Title: Broadcasting on directed acyclic graphs

Abstract: Consider an infinite directed acyclic graph (DAG) with a unique source node X. Let the collection of nodes at distance k from X be called the kth layer. At time zero, the source node is given a bit. At time k each node in the (k - 1)th layer inspects its inputs and sends a bit to its descendants in the kth layer.  Each sent bit is flipped with a probability of error $\delta$. The goal is to be able to recover X with probability of error better than 1/2 from the values of all nodes at an arbitrarily deep layer k. The classical example of trees shows existence of a critical $\delta$ beyond which recovery is impossible. This talk is about locating this threshold for other graphs: random-like and regular 2D and 3D grids. A tacit conjecture stimulating this work is that broadcasting is impossible in 2D and possible in 3D grids. I will talk about our steps towards resolving it. Joint work with Anuran Makur and Elchanan Mossel.