The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels

Berkeley, California October 21-October 24

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.76

47th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Christian Borgs Articles by Jennifer Chayes Articles by Elchanan Mossel Articles by Sebastien Roch

	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, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.