Abstract
This paper shows that the logarithm of the number of solutions of a random planted -SAT formula concentrates around a deterministic -independent threshold. Specifically, if is a random -SAT formula on variables, with clause density and with a uniformly drawn planted solution, there exists a function such that, besides for some in a set of Lesbegue measure zero, we have in probability, where is the number of solutions of the formula . This settles a problem left open in Abbe-Montanari RANDOM 2013, where the concentration is obtained only for the expected logarithm over the clause distribution. The result is also extended to a more general class of random planted CSPs; in particular, it is shown that the number of pre-images for the Goldreich one-way function model concentrates for some choices of the predicates.
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.