Fetching the paper…
Reading the bibliography…
We show that throughout the satisfiable phase the normalised number of satisfying assignments of a random $2$-SAT formula converges in probability to an expression predicted by the cavity method from statistical physics.
L. Valiant: The complexity of enumeration and reliability problems. SIAM Journal on Computing 8
1979
Earlier work this paper cites.
B. Bollobás: The evolution of random graphs. Transactions of the AMS 286
1984
Earlier work this paper cites.
W. Dowling, J. Gallier: Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming 1
1984
Earlier work this paper cites.
T. Łuczak: Component behavior near the critical point of the random graph process. Random Structures and Algorithms 1
1990
Earlier work this paper cites.
P. Cheeseman, B. Kanefsky, W. Taylor: Where the really
1991
Earlier work this paper cites.
V. Chvátal, B. Reed: Mick gets some (the odds are on his side). Proc. 33th FOCS (1992) 620–627
1992
Earlier work this paper cites.
A. Goerdt: A threshold for unsatisfiability. J. Comput. Syst. Sci. 53
1996
Earlier work this paper cites.
R. Monasson, R. Zecchina: The entropy of the k k -satisfiability problem. Phys. Rev. Lett. 76
1996
Earlier work this paper cites.
R. Monasson, R. Zecchina: Statistical mechanics of the random K K -SAT model. Phys. Rev. E 56
1997
Earlier work this paper cites.
Y. Boufkhad, O. Dubois: Length of prime implicants and number of solutions of random CNF formulae. Theoretical Computer Science 215
1999
Earlier work this paper cites.
A. Sharell: Concentration of the number of solutions to a random 2-CNF formula. Manuscript (2000)
2000
Earlier work this paper cites.
D. Achlioptas, A. Chtcherba, G. Istrate, C. Moore: The phase transition in 1-in- k k SAT and NAE 3-SAT. Proc. 12th SODA (2001) 721–722
2001
Earlier work this paper cites.
B. Bollobás, C. Borgs J. Chayes, J. Kim, D. Wilson: The scaling window of the 2 2 -SAT transition. Random Structures and Algorithms 18
2001
Earlier work this paper cites.
W. Fernandez de la Vega: Random 2-SAT: results and problems. Theoretical Computer Science 265
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.
O. Dubois, J. Mandler: The 3-XORSAT threshold. Proc. 43rd FOCS (2002) 769–778
2002
Earlier work this paper cites.
M. Mézard, G. Parisi, R. Zecchina: Analytic and algorithmic solution of random satisfiability problems. Science 297
2002
Cited alongside, same era.
M. Aizenman, R. Sims, S. Starr: An extended variational principle for the SK spin-glass model. Phys. Rev. B 68
2003
Cited alongside, same era.
S. Franz, M. Leone: Replica bounds for optimization problems and diluted spin systems. J. Stat. Phys. 111
2003
Cited alongside, same era.
F. Guerra: Broken replica symmetry bounds in the mean field spin glass model. Comm. Math. Phys. 233
2003
Cited alongside, same era.
D. Achlioptas, Y. Peres: The threshold for random k k -SAT is 2 k ln 2 − O ( k ) 2^{k}\ln 2-O(k) . Journal of the AMS 17
2004
Cited alongside, same era.
V. Bogachev, A. Kolesnikov: The Monge-Kantorovich problem: achievements, connections, and perspectives. Russian Mathematical Surveys 67
2012
Later among the works it cites.
A. Dembo, A. Montanari, N. Sun: Factor models on locally tree-like graphs. Annals of Probability 41
2013
Later among the works it cites.
D. Panchenko: Spin glass models from the point of view of spin distributions. Annals of Probability 41
2013
Later among the works it cites.
E. Abbe, A. Montanari: On the concentration of the number of solutions of random satisfiability formulas. Random Structures and Algorithms 45
2014
Later among the works it cites.
D. Panchenko: On the replica symmetric solution of the K K -sat model. Electron. J. Probab. 19
2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
D. Coppersmith, D. Gamarnik, M. Hajiaghayi, G. Sorkin: Random MAX SAT, random MAX CUT, and their phase transitions. Random Structures and Algorithms 24
2004
Cited alongside, same era.
D. Panchenko, M. Talagrand: Bounds for diluted mean-fields spin glass models. Probab. Theory Relat. Fields 130
2004
Cited alongside, same era.
D. Achlioptas, C. Moore: Random k k -SAT: two moments suffice to cross a sharp threshold. SIAM Journal on Computing 36
2006
Cited alongside, same era.
A. Scott, G. Sorkin: Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time. Combinatorics, Probability and Computing 15
2006
Cited alongside, same era.
C. Cooper, A. Frieze, G. Sorkin: Random 2 2 -SAT with prescribed literal degrees. Algorithmica 48
2007
Cited alongside, same era.
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
Cited alongside, same era.
A. Montanari, F. Ricci-Tersenghi, G. Semerjian: Solving constraint satisfaction problems through Belief Propagation-guided decimation. Proc. 45th Allerton (2007)
2007
Cited alongside, same era.
J. Ding, A. Sly, N. Sun: Proof of the satisfiability conjecture for large k k . Proc. 47th STOC (2015) 59–68
2015
Later among the works it cites.
N. Alon, J. Spencer: The probabilistic method. Wiley (2016)
2016
Later among the works it cites.
A. Barvinok: Combinatorics and complexity of partition functions. Springer (2016)
2016
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: Satisfiability threshold for random regular NAE-SAT. Communications in Mathematical Physics 341
2016
Later among the works it cites.
B. Pittel, G. Sorkin: The satisfiability threshold for k k -XORSAT. Combinatorics, Probability and Computing 25
2016
Later among the works it cites.
A. Sly, N. Sun, Y. Zhang: The number of solutions for random regular NAE-SAT. Proc. 57th FOCS (2016) 724–731
2016
Later among the works it cites.
A. Coja-Oghlan, F. Krzakala, W. Perkins, L. Zdeborová: Information-theoretic thresholds from the cavity method. Advances in Mathematics 333
2018
Later among the works it cites.
A. Coja-Oghlan, N. Wormald: The number of satisfying assignments of random regular k k -SAT formulas. Combinatorics, Probability and Computing 27
2018
Later among the works it cites.
F. Rassmann: On the number of solutions in random graph k k -colouring. Combinatorics, Probability and Computing 28
2019
Later among the works it cites.