Reconstruction threshold for the hardcore model

Nayantara Bhatnagar; Allan Sly; Prasad Tetali

doi:10.1007/978-3-642-15369-3_33

Reconstruction threshold for the hardcore model

Nayantara Bhatnagar, Allan Sly, Prasad Tetali

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Scopus citations

Abstract

In this paper we consider the reconstruction problem on the tree for the hardcore model. We determine new bounds for the non-reconstruction regime on the k-regular tree showing non-reconstruction when λ < (ln2-o(1)1n ² k/2lnlnk improving the previous best bound of λ<e-1. This is almost tight as reconstruction is known to hold when λ>(e+o(1)) ln² k. We discuss the relationship for finding large independent sets in sparse random graphs and to the mixing time of Markov chains for sampling independent sets on trees.

Original language	English (US)
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings
Pages	434-447
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-15369-3_33
State	Published - 2010
Externally published	Yes
Event	13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 - Barcelona, Spain Duration: Sep 1 2010 → Sep 3 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6302 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
Country/Territory	Spain
City	Barcelona
Period	9/1/10 → 9/3/10

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-15369-3_33

Cite this

Bhatnagar, N., Sly, A., & Tetali, P. (2010). Reconstruction threshold for the hardcore model. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings (pp. 434-447). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6302 LNCS). https://doi.org/10.1007/978-3-642-15369-3_33

Bhatnagar, Nayantara ; Sly, Allan ; Tetali, Prasad. / Reconstruction threshold for the hardcore model. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. 2010. pp. 434-447 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{61abe483e95241e0b26340d7494acd94,

title = "Reconstruction threshold for the hardcore model",

abstract = "In this paper we consider the reconstruction problem on the tree for the hardcore model. We determine new bounds for the non-reconstruction regime on the k-regular tree showing non-reconstruction when λ < (ln2-o(1)1n 2 k/2lnlnk improving the previous best bound of λ(e+o(1)) ln2 k. We discuss the relationship for finding large independent sets in sparse random graphs and to the mixing time of Markov chains for sampling independent sets on trees.",

author = "Nayantara Bhatnagar and Allan Sly and Prasad Tetali",

year = "2010",

doi = "10.1007/978-3-642-15369-3_33",

language = "English (US)",

isbn = "3642153682",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "434--447",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

note = "13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 ; Conference date: 01-09-2010 Through 03-09-2010",

}

Bhatnagar, N, Sly, A & Tetali, P 2010, Reconstruction threshold for the hardcore model. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6302 LNCS, pp. 434-447, 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010, Barcelona, Spain, 9/1/10. https://doi.org/10.1007/978-3-642-15369-3_33

Reconstruction threshold for the hardcore model. / Bhatnagar, Nayantara; Sly, Allan; Tetali, Prasad.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. 2010. p. 434-447 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6302 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Reconstruction threshold for the hardcore model

AU - Bhatnagar, Nayantara

AU - Sly, Allan

AU - Tetali, Prasad

PY - 2010

Y1 - 2010

N2 - In this paper we consider the reconstruction problem on the tree for the hardcore model. We determine new bounds for the non-reconstruction regime on the k-regular tree showing non-reconstruction when λ < (ln2-o(1)1n 2 k/2lnlnk improving the previous best bound of λ(e+o(1)) ln2 k. We discuss the relationship for finding large independent sets in sparse random graphs and to the mixing time of Markov chains for sampling independent sets on trees.

AB - In this paper we consider the reconstruction problem on the tree for the hardcore model. We determine new bounds for the non-reconstruction regime on the k-regular tree showing non-reconstruction when λ < (ln2-o(1)1n 2 k/2lnlnk improving the previous best bound of λ(e+o(1)) ln2 k. We discuss the relationship for finding large independent sets in sparse random graphs and to the mixing time of Markov chains for sampling independent sets on trees.

UR - http://www.scopus.com/inward/record.url?scp=78149314594&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78149314594&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15369-3_33

DO - 10.1007/978-3-642-15369-3_33

M3 - Conference contribution

AN - SCOPUS:78149314594

SN - 3642153682

SN - 9783642153686

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 434

EP - 447

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010

Y2 - 1 September 2010 through 3 September 2010

ER -

Bhatnagar N, Sly A, Tetali P. Reconstruction threshold for the hardcore model. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. 2010. p. 434-447. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-15369-3_33

Reconstruction threshold for the hardcore model

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this