Joint Colloquium with Stanford Algorithms Seminar

Reconstruction Problems on Trees: A Simple Criterion for Impossibility

Alistair Sinclair
Department of Electrical Engineering and Computer Science
University of California, Berkeley


Wednesday, March 7, 2007
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

Consider a communication network consisting of a complete regular tree whose edges are independent noisy channels. A value is transmitted down the tree from the root. For what values of the channel noise parameters can the transmitted value be reconstructed from the values observed at the leaves? Reconstruction problems on trees have been widely studied in both communication theory and genetics.

In this talk I will present a simple criterion for determining bounds on the range of parameter values for which reconstruction is not possible. This leads to easy, unified proofs of known bounds, and in some cases to improvements, for a number of channels. The same criterion also implies rapid mixing of the Glauber dynamics for associated statistical mechanical models on trees.

Joint work with Fabio Martinelli and Dror Weitz.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html