Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates

2015/04/30 by Abbe, Emmanuel, Edwards, Katherine
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1504.08316

Abstract

This paper shows that the logarithm of the number of solutions of a random planted k-SAT formula concentrates around a deterministic n-independent threshold. Specifically, if F^*_k(α,n) is a random k-SAT formula on n variables, with clause density α and with a uniformly drawn planted solution, there exists a function ϕ_k(⋅) such that, besides for some α in a set of Lesbegue measure zero, we have (1)/(n)log Z(F^*_k(α,n)) → ϕ_k(α) in probability, where Z(F) is the number of solutions of the formula F. 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.

Related

• On the concentration of the number of solutions of random satisfiability formulas
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Counting solutions to random CNF formulas
• The number of random 2-SAT solutions is asymptotically log-normal
• The Threshold for Random k-SAT is 2^k ln2 - O(k)