Abstract
Let be the number of solutions of a random -satisfiability formula with variables and clause density . Assume that the probability that 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 , with high probability. In particular, the assumption holds for all , which proves the above concentration claim in the whole satisfiability regime of random -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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.