Phase Transitions in Reconstruction
Phase Transitions in Computation and Reconstruction
March 07, 2005 10:00 AM to 10:50 AM
Speakers:
|
 |
Abstract: |
From a central node in a network, information is sent to some output
nodes via noisy channels. When can the original information be reconstructed
(with some probability better than a purely random guess) given the data
at the output nodes? This type of problem, in the relatively simple case
of tree networks, occurs in information theory, mathematical genetics,
statistical physics (spin glasses) and other areas. In many cases there
is a phase transition as the noise parameter (or mutation rate) varies:
beyond a certain noise threshold, reconstruction becomes exponentially
difficult. The precise transition point is known in only in one case. I
will survey the area starting with the work of Spitzer, Kamae and others
from the 1970's and mention the similarities and differences with
phylogenetic reconstruction and reconstruction from observing a hidden
Markov model. Later talks in the workshop will describe the state of the
art in this field. |
Keywords: |
Phase Transition;Computation;Reconstruction |
|
|
