loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels
Berkeley, California
October 21-October 24
ISBN: 0-7695-2720-5
ASCII Text
x 
 
Christian Borgs, Jennifer Chayes, Elchanan Mossel, Sebastien Roch, "The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels," Foundations of Computer Science, IEEE Annual Symposium on, pp. 518-530, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2006.76,
author = {Christian Borgs and Jennifer Chayes and Elchanan Mossel and Sebastien Roch},
title = {The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2006},
issn = {0272-5428},
pages = {518-530},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.76},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels
SN - 0272-5428
SP518
EP530
A1 - Christian Borgs,
A1 - Jennifer Chayes,
A1 - Elchanan Mossel,
A1 - Sebastien Roch,
PY - 2006
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Christian Borgs, Microsoft Research
Jennifer Chayes, Microsoft Research
Elchanan Mossel, UC Berkeley, USA
Sebastien Roch, UC Berkeley, USA
We establish the exact threshold for the reconstruction problem for a binary asymmetric channel on the b-ary tree, provided that the asymmetry is sufficiently small. This is the first exact reconstruction threshold obtained in roughly a decade. We discuss the implications of our result for Glauber dynamics, phylogenetic reconstruction, noisy communication and the so-called "replica symmetry breaking" in spin glasses and random satisfiability problems.
Citation:
Christian Borgs, Jennifer Chayes, Elchanan Mossel, Sebastien Roch, "The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels," focs, pp.518-530, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.