2010/06/18 by Emmanuel Abbe, Emmanuel Abbé, Andrea Montanari +2 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Logic in Computer Science (cs.LO) #Probability (math.PR) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #cs.CC #cs.DM #cs.LO #math.PR
paper · pdf · doi:10.48550/arxiv.1006.3786
arxiv created 2010/06/18 · openalex publication_date 2010/06/18 · arxiv updated 2010/06/23 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
Let Z(F) be the number of solutions of a random k-satisfiability formula F with n variables and clause density α. Assume that the probability that F is unsatisfiable is O(1/log(n)1+\e) for \e>0. We show that (possibly excluding a countable set of `exceptional' α's) the number of solutions concentrate in the logarithmic scale, i.e., there exists a non-random function ϕ(α) such that, for any δ>0, (1/n)log Z(F)∈ [ϕ-δ,ϕ+δ] with high probability. In particular, the assumption holds for all α<1, which proves the above concentration claim in the whole satisfiability regime of random 2-SAT. We also extend these results to a broad class of constraint satisfaction problems. The proof is based on an interpolation technique from spin-glass theory, and on an application of Friedgut's theorem on sharp thresholds for graph properties.