Fetching the paper…
Reading the bibliography…
In a broad class of sparse random constraint satisfaction problems(CSP), deep heuristics from statistical physics predict that there is a condensation phase transition before the satisfiability threshold, governed by one-step replica symmetry breaking(1RSB).
Solvable model of a spin-glass
Sherrington, D., and Kirkpatrick, S · 1975
Earlier work this paper cites.
Mick gets some (the odds are on his side) (satisfiability)
Chvatal, V., and Reed, B · 1992
Earlier work this paper cites.
The spherical p-spin interaction spin glass model: the statics
Crisanti, A., and Sommers, H. J · 1992
Earlier work this paper cites.
Hardy-Ramanujan’s asymptotic formula for partitions and the central limit theorem
Báez-Duarte, L · 1997
Earlier work this paper cites.
Approximating the unsatisfiability threshold of random formulas
Kirousis, L. M., Kranakis, E., Krizanc, D., and Stamatiou, Y. C · 1998
Earlier work this paper cites.
The phase transition in 1-in- k k SAT and NAE 3-sat
Achlioptas, D., Chtcherba, A., Istrate, G., and Moore, C · 2001
Earlier work this paper cites.
The scaling window of the 2-SAT transition
Bollobás, B., Borgs, C., Chayes, J. T., Kim, J. H., and Wilson, D. B · 2001
Earlier work this paper cites.
The 3-XORSAT threshold
Dubois, O., and Mandler, J · 2002
Earlier work this paper cites.
Analytic and algorithmic solution of random satisfiability problems
Mézard, M., Parisi, G., and Zecchina, R · 2002
Earlier work this paper cites.
On the nature of the low-temperature phase in discontinuous mean-field spin glasses
Montanari, A., and Ricci-Tersenghi, F · 2003
Earlier work this paper cites.
The threshold for random k k -SAT is 2 k log 2 − O ( k ) 2^{k}\log 2-O(k)
Achlioptas, D., and Peres, Y · 2004
Earlier work this paper cites.
Threshold values, stability analysis, and high- q q asymptotics for the coloring problem on random graphs
Krz̧akała, F., Pagnani, A., and Weigt, M · 2004
Earlier work this paper cites.
The two possible values of the chromatic number of a random graph
Achlioptas, D., and Naor, A · 2005
Earlier work this paper cites.
Rigorous location of phase transitions in hard optimization problems
Achlioptas, D., Naor, A., and Peres, Y · 2005
Earlier work this paper cites.
Random k k -SAT: two moments suffice to cross a sharp threshold
Achlioptas, D., and Moore, C · 2006
Earlier work this paper cites.
The Parisi formula
Talagrand, M · 2006
Earlier work this paper cites.
Reconstruction for models on random graphs
Gerschenfeld, A., and Montanari, A · 2007
Earlier work this paper cites.
Gibbs states and the set of solutions of random constraint satisfaction problems
Krz̧akała, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G., and Zdeborová, L · 2007
Cited alongside, same era.
Phase transitions in the coloring of random graphs
Zdeborová, L., and Krz̧akała, F · 2007
Cited alongside, same era.
Clusters of solutions and replica symmetry breaking in random k k -satisfiability
Montanari, A., Ricci-Tersenghi, F., and Semerjian, G · 2008
Cited alongside, same era.
Analytic combinatorics
Flajolet, P., and Sedgewick, R · 2009
Cited alongside, same era.
Information, physics, and computation
Mézard, M., and Montanari, A · 2009
Cited alongside, same era.
Large deviations techniques and applications
Dembo, A., and Zeitouni, O · 2010
Cited alongside, same era.
On the chromatic number of random regular graphs
Coja-Oghlan, A., Efthymiou, C., and Hetterich, S · 2016
Later among the works it cites.
The asymptotic k k -SAT threshold
Coja-Oghlan, A., and Panagiotou, K · 2016
Later among the works it cites.
Maximum independent sets on random regular graphs
Ding, J., Sly, A., and Sun, N · 2016
Later among the works it cites.
Satisfiability threshold for random regular NAE-SAT
Ding, J., Sly, A., and Sun, N · 2016
Later among the works it cites.
The satisfiability threshold for k k -XORSAT
Pittel, B., and Sorkin, G. B · 2016
Later among the works it cites.
Generalization and refinement of the integro-local stone theorem for sums of random vectors
Borovkov, A. A · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Tight thresholds for cuckoo hashing via XORSAT
Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., and Rink, M · 2010
Cited alongside, same era.
Reconstruction and clustering in random constraint satisfaction problems
Montanari, A., Restrepo, R., and Tetali, P · 2011
Cited alongside, same era.
Catching the k k -NAESAT threshold [extended abstract]
Coja-Oghlan, A., and Panagiotou, K · 2012
Cited alongside, same era.
The condensation transition in random hypergraph 2-coloring
Coja-Oghlan, A., and Zdeborová, L · 2012
Cited alongside, same era.
The hard-core model on random graphs revisited
Barbier, J., Krz̧akała, F., Zdeborová, L., and Zhang, P · 2013
Cited alongside, same era.
Upper-bounding the k k -colorability threshold by counting covers
Coja-Oghlan, A · 2013
Cited alongside, same era.
The geometry of the Gibbs measure of pure spherical spin glasses
Subag, E · 2017
Later among the works it cites.
The extremal process of critical points of the pure p-spin spherical spin glass model
Subag, E., and Zeitouni, O · 2017
Later among the works it cites.
Information-theoretic thresholds from the cavity method
Coja-Oghlan, A., Krz̧akała, F., Perkins, W., and Zdeborová, L · 2018
Later among the works it cites.
Existence of two-step replica symmetry breaking for the spherical mixed p-spin glass at zero temperature
Auffinger, A., and Zeng, Q · 2019
Later among the works it cites.
Breaking of 1RSB in random MAX-NAE-SAT
Bartha, Z., Sun, N., and Zhang, Y · 2019
Later among the works it cites.
The SK model is infinite step replica symmetry breaking at zero temperature
Auffinger, A., Chen, W.-K., and Zeng, Q · 2020
Closest in time.
The satisfiability threshold for random linear equations
Ayre, P., Coja-Oghlan, A., Gao, P., and Müller, N · 2020
Closest in time.
The asymptotics of the clustering transition for random constraint satisfaction problems
Budzynski, L., and Semerjian, G · 2020
Closest in time.
Asymptotic formula of the number of Newton polygons
Harashita, S · 2021
Closest in time.
The number of solutions for random regular nae-sat
Sly, A., Sun, N., and Zhang, Y · 2022
Closest in time.
The number of solutions for random regular NAE-SAT
Sly, A., Sun, N., and Zhang, Y · 2023
Closest in time.