{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:04:23Z","timestamp":1725563063972},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_33","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"434-447","source":"Crossref","is-referenced-by-count":5,"title":["Reconstruction Threshold for the Hardcore Model"],"prefix":"10.1007","author":[{"given":"Nayantara","family":"Bhatnagar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Allan","family":"Sly","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasad","family":"Tetali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Coja-Oghlan, A.: Algorithmic barriers from phase transitions. In: Proceedings of IEEE FOCS 2008, pp. 793\u2013802 (2008)","DOI":"10.1109\/FOCS.2008.11"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00440-004-0369-4","volume":"131","author":"N. Berger","year":"2005","unstructured":"Berger, N., Kenyon, C., Mossel, E., Peres, Y.: Glauber dynamics on trees and hyperbolic graphs. Probability Theory and Related Fields\u00a0131, 311\u2013340 (2005)","journal-title":"Probability Theory and Related Fields"},{"key":"33_CR3","unstructured":"Bhatnagar, N., Vera, J., Vigoda, E., Weitz, D.: Reconstruction for colorings on trees. To appear in SIAM Journal on Discrete Mathematics"},{"key":"33_CR4","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/BF02179399","volume":"79","author":"P.M. Bleher","year":"1995","unstructured":"Bleher, P.M., Ruiz, J., Zagrebnov, V.A.: On the purity of limiting gibbs state for the Ising model on the Bethe lattice. Journal of Statistical Physics\u00a079, 473\u2013482 (1995)","journal-title":"Journal of Statistical Physics"},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J., Mossel, E., Roch, S.: The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels. In: Proceedings of IEEE FOCS 2006, pp. 518\u2013530 (2006)","DOI":"10.1109\/FOCS.2006.76"},{"key":"33_CR6","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1017\/S0963548302005254","volume":"11","author":"C. Cooper","year":"2002","unstructured":"Cooper, C., Frieze, A., Reed, B., Riordan, O.: Random regular graphs of non-Constant degree: Independence and Chromatic Number. Combinatorics, Probability and Computing\u00a011, 323\u2013341 (2002)","journal-title":"Combinatorics, Probability and Computing"},{"key":"33_CR7","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1002\/rsa.20006","volume":"24","author":"G. Brightwell","year":"2004","unstructured":"Brightwell, G., Winkler, P.: A second threshold for the hard-core model on a Bethe lattice. Random structures and algorithms\u00a024, 303\u2013314 (2004)","journal-title":"Random structures and algorithms"},{"key":"33_CR8","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mossel, E., Roch, S.: Optimal phylogenetic reconstruction. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 159\u2013168 (2006)","DOI":"10.1145\/1132516.1132540"},{"key":"33_CR9","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00220-009-0978-y","volume":"295","author":"J. Ding","year":"2010","unstructured":"Ding, J., Lubetzky, E., Peres, Y.: Mixing time of critical Ising model on trees is polynomial in the height. Communications in Mathematical Physics\u00a0295, 161\u2013207 (2010)","journal-title":"Communications in Mathematical Physics"},{"key":"33_CR10","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1214\/aoap\/1019487349","volume":"10","author":"W. Evans","year":"2000","unstructured":"Evans, W., Kenyon, C., Peres, Y., Schulman, L.J.: Broadcasting on trees and the Ising model. Annals of Applied Probabability\u00a010, 410\u2013433 (2000)","journal-title":"Annals of Applied Probabability"},{"key":"33_CR11","volume-title":"Inferring Phylogenies","author":"J. Felsenstein","year":"2004","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer, New York (2004)"},{"key":"33_CR12","doi-asserted-by":"crossref","DOI":"10.1515\/9783110850147","volume-title":"Gibbs measures and phase transitions","author":"H.O. Georgii","year":"1988","unstructured":"Georgii, H.O.: Gibbs measures and phase transitions. Walter de Gruyter, Berlin (1988)"},{"key":"33_CR13","doi-asserted-by":"publisher","first-page":"2630","DOI":"10.1214\/009117904000000153","volume":"32","author":"S. Janson","year":"2004","unstructured":"Janson, S., Mossel, E.: Robust reconstruction on trees is determined by the second eigenvalue. Annals of Probability\u00a032, 2630\u20132649 (2004)","journal-title":"Annals of Probability"},{"key":"33_CR14","doi-asserted-by":"publisher","first-page":"10318","DOI":"10.1073\/pnas.0703685104","volume":"104","author":"F. Krz\u0327aka\u0142a","year":"2007","unstructured":"Krz\u0327aka\u0142a, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G., Zdeborov\u00e1, L.: Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences\u00a0104, 10318 (2007)","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"33_CR15","doi-asserted-by":"publisher","first-page":"1463","DOI":"10.1214\/aoms\/1177699139","volume":"37","author":"H. Kesten","year":"1966","unstructured":"Kesten, H., Stigum, B.P.: Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Annals of Mathematical Statistics\u00a037, 1463\u20131481 (1966)","journal-title":"Annals of Mathematical Statistics"},{"key":"33_CR16","doi-asserted-by":"crossref","unstructured":"Martin, J.: Reconstruction thresholds on regular trees. In: Banderier, C., Krattenthaler, C. (eds.) Discrete Random Walks, DRW 2003. Discrete Mathematics and Theoretical Computer Science Proceedings, pp. 191\u2013204 (2003)","DOI":"10.46298\/dmtcs.3325"},{"key":"33_CR17","unstructured":"Martinelli, F., Sinclair, A., Weitz, D.: Fast mixing for independent sets, colorings, and other models on trees. In: Proceedings of ACM-SIAM SODA, pp. 449\u2013458 (2004)"},{"key":"33_CR18","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s00220-004-1147-y","volume":"250","author":"F. Martinelli","year":"2004","unstructured":"Martinelli, F., Sinclair, A., Weitz, D.: Glauber dynamics on trees: boundary conditions and mixing time. Communications in Mathematical Physics\u00a0250, 301\u2013334 (2004)","journal-title":"Communications in Mathematical Physics"},{"key":"33_CR19","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1007\/s10955-006-9162-3","volume":"124","author":"M. M\u00e9zard","year":"2006","unstructured":"M\u00e9zard, M., Montanari, A.: Reconstruction on trees and spin glass transition. Journal of Statistical Physics\u00a0124, 1317\u20131350 (2006)","journal-title":"Journal of Statistical Physics"},{"key":"33_CR20","unstructured":"Montanari, A., Restrepo, R., Tetali, P.: Reconstruction and Clustering Thresholds for Random Constraint Satisfaction Problems (2009) (preprint)"},{"key":"33_CR21","series-title":"DIMACS series in discrete mathematics and theoretical computer science","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1090\/dimacs\/063\/12","volume-title":"Graphs, Morphisms and Statistical Physics","author":"E. Mossel","year":"2004","unstructured":"Mossel, E.: Survey: Information flow on trees. In: Nestril, J., Winkler, P. (eds.) Graphs, Morphisms and Statistical Physics. DIMACS series in discrete mathematics and theoretical computer science, pp. 155\u2013170. Amer. Math. Soc., Providence (2004)"},{"key":"33_CR22","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1214\/aoap\/998926994","volume":"11","author":"E. Mossel","year":"2001","unstructured":"Mossel, E.: Reconstruction on trees: beating the second eigenvalue. Annals of Applied Probabability\u00a011, 285\u2013300 (2001)","journal-title":"Annals of Applied Probabability"},{"key":"33_CR23","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1214\/aoap\/1060202828","volume":"13","author":"E. Mossel","year":"2003","unstructured":"Mossel, E., Peres, Y.: Information flow on trees. Annals of Applied Probabability\u00a013, 817\u2013844 (2003)","journal-title":"Annals of Applied Probabability"},{"key":"33_CR24","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/s00220-009-0783-7","volume":"288","author":"A. Sly","year":"2009","unstructured":"Sly, A.: Reconstruction of random colourings. Communications of Mathematical Physics\u00a0288, 943\u2013961 (2009)","journal-title":"Communications of Mathematical Physics"},{"key":"33_CR25","doi-asserted-by":"crossref","unstructured":"Sly, A.: Reconstruction of symmetric Potts Models. In: Proceedings of the 41st ACM Symposium on Theory of Computing, pp. 581\u2013590 (2009)","DOI":"10.1145\/1536414.1536493"},{"key":"33_CR26","doi-asserted-by":"crossref","unstructured":"Tetali, P., Vera, J., Vigoda, E., Yang, L.: Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1646\u20131656 (2010)","DOI":"10.1137\/1.9781611973075.134"},{"key":"33_CR27","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N. Wormald","year":"1995","unstructured":"Wormald, N.: Differential equations for random processes and random graphs. Annals of Applied Probability\u00a05, 1217\u20131235 (1995)","journal-title":"Annals of Applied Probability"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,7]],"date-time":"2021-11-07T11:41:48Z","timestamp":1636285308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}