Fetching the paper…
Reading the bibliography…
We verify a key component of the replica symmetry breaking hypothesis put forward in the physics literature [M\'ezard and Montanari 2009] on random factor graph models.
E. Szemerédi: Regular partitions of graphs. Colloq. Internat. CNRS 260
1978
Earlier work this paper cites.
M. Mézard, G. Parisi, M. Virasoro: Spin glass theory and beyond. World Scientific 1987
1987
Earlier work this paper cites.
A. Frieze, R. Kannan: Quick approximation to matrices and applications. Combinatorica 19
1999
Earlier work this paper cites.
E. Marinari, G. Parisi, F. Ricci-Tersenghi, J. Ruiz-Lorenzo, F. Zuliani: Replica symmetry breaking in short-range spin glasses: theoretical foundations and numerical evidences. Journal of Statistical Physics 98
2000
Earlier work this paper cites.
M. Mézard, G. Parisi: The Bethe lattice spin glass revisited. Eur. Phys. J. B 20
2001
Earlier work this paper cites.
M. Talagrand: The high temperature case for the random K K -sat problem. Probab. Theory Related Fields 119
2001
Earlier work this paper cites.
M. Mézard, G. Parisi, R. Zecchina: Analytic and algorithmic solution of random satisfiability problems. Science 297
2002
Earlier work this paper cites.
M. Mézard, G. Parisi: The cavity method at zero temperature. Journal of Statistical Physics 111
2003
Earlier work this paper cites.
L. Lovász, B. Szegedy: Limits of dense graph sequences. Journal of Combinatorial Theory, Series B 96
2006
Earlier work this paper cites.
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, L. Zdeborová: Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. National Academy of Sciences 104
2007
Earlier work this paper cites.
C. Borgs, J. Chayes, L. Lovász, V. Sós, K. Vesztergombi: Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics 219
2008
Earlier work this paper cites.
P. Diaconis, S. Janson: Graph limits and exchangeable random graphs. Rend. Mat. Appl. 28
2008
Earlier work this paper cites.
A. Montanari: Estimating random variables from random sparse observations. European Transactions on Telecommunications 19
2008
Earlier work this paper cites.
T. Richardson, R. Urbanke: Modern coding theory. Cambridge University Press (2008)
2008
Earlier work this paper cites.
M. Mézard, A. Montanari: Information, physics and computation. Oxford University Press 2009
2009
Earlier work this paper cites.
E. Mossel, D. Weitz, N. Wormald: On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields 143
2009
Cited alongside, same era.
A. Dembo, A. Montanari: Gibbs measures and phase transitions on sparse random graphs. Brazilian Journal of Probability and Statistics 24
2010
Cited alongside, same era.
P. Raghavendra, N. Tan: Approximating CSPs with global cardinality constraints using SDP hierarchies. Proc. 23rd SODA (2012) 373–387
2012
Cited alongside, same era.
P. Contucci, S. Dommers, C. Giardina, S. Starr: Antiferromagnetic Potts model on the Erdős-Rényi random graph. Communications in Mathematical Physics 323
2013
Cited alongside, same era.
A. Dembo, A. Montanari, N. Sun: Factor models on locally tree-like graphs. Annals of Probability 41
2013
Cited alongside, same era.
2016
Later among the works it cites.
J. Banks, C. Moore, J. Neeman, P. Netrapalli: Information-theoretic thresholds for community detection in sparse networks. Proc. 29th COLT (2016) 383–416
2016
Later among the works it cites.
V. Bapst, A. Coja-Oghlan: Harnessing the Bethe free energy. Random Structures and Algorithms 49
2016
Later among the works it cites.
J. Barbier, M. Dia, N. Macris: Threshold saturation of spatially coupled sparse superposition codes for all memoryless channels. IEEE Information Theory Workshop (2016)
2016
Later among the works it cites.
A. Coja-Oghlan, N. Jaafari: On the Potts antiferromagnet on random graphs. Electronic Journal of Combinatorics 23
2016
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
S. Janson: Graphons, cut norm and distance, couplings and rearrangements. NYJM Monographs, Volume 4, 2013
2013
Cited alongside, same era.
D. Panchenko: The Sherrington-Kirkpatrick model. Springer 2013
2013
Cited alongside, same era.
A. Dembo, A. Montanari, A. Sly, N. Sun: The replica symmetric solution for Potts models on d-regular graphs. Communications in Mathematical Physics 327
2014
Cited alongside, same era.
L. Massoulié: Community detection thresholds and the weak Ramanujan property. Proceedings of the 46th Annual ACM Symposium on Theory of Computing (2014) 694–703
2014
Cited alongside, same era.
E. Mossel, J. Neeman, A. Sly: Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields (2014) 1–31
2014
Cited alongside, same era.
D. Panchenko: On the replica symmetric solution of the K K -sat model. Electron. J. Probab. 19
2014
Cited alongside, same era.
A. Sly, N. Sun: The computational hardness of counting in two-spin models on d d -regular graphs. Annals of Probability 42
2014
Cited alongside, same era.
Later among the works it cites.
A. Coja-Oghlan, K. Panagiotou: The asymptotic k k -SAT threshold. Advances in Mathematics 288
2016
Later among the works it cites.
J. Ding, A. Sly, N. Sun: Maximum independent sets on random regular graphs. Acta Mathematica 217
2016
Later among the works it cites.
A. Galanis, D. Stefankovic, E. Vigoda: Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Combinatorics, Probabability and Computing 25
2016
Later among the works it cites.
A. Giurgiu, N. Macris, R. Urbanke: Spatial coupling as a proof technique and three applications. IEEE Transactions on Information Theory 62
2016
Later among the works it cites.
A. Coja-Oghlan, W. Perkins, K. Skubch: Limits of discrete distributions and Gibbs measures on random graphs. European Journal of Combinatorics 66
2017
Closest in time.
E. Abbe, C. Sandon: Proof of the achievability conjectures for the general stochastic block model. Communications on Pure and Applied Mathematics 71
2018
Closest in time.
A. Coja-Oghlan, F. Krzakala, W. Perkins, L. Zdeborová: Information-theoretic thresholds from the cavity method. Advances in Mathematics 333
2018
Closest in time.
A. Coja-Oghlan, W. Perkins: Belief Propagation on replica symmetric random factor graph models. Annales de l’Institut Henri Poincare D 5
2018
Closest in time.
E. Mossel, J. Neeman, A. Sly: A proof of the block model threshold conjecture. Combinatorica 38
2018
Closest in time.