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

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^{\ast }(\alpha ,n)$ is a random $k$-SAT formula on $n$ variables, with clause density $\alpha$ and with a uniformly drawn planted solution, there exists a function ${\varphi }_k(\cdot )$ such that, besides for some $\alpha$ in a set of Lesbegue measure zero, we have $\frac{1}{n}\log Z(F_k^{\ast }(\alpha ,n))\to {\varphi }_k(\alpha )$ 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.

arXiv comment17 pages

References in corpus (13)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Replica bounds for diluted non-Poissonian spin systems
• The condensation transition in random hypergraph 2-coloring
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
• Quiet Planting in the Locked Constraint Satisfaction Problems
• The Satisfiability Threshold for k-XORSAT
• Hiding Satisfying Assignments: Two are Better than One
• Tight Thresholds for Cuckoo Hashing via XORSAT
• On the concentration of the number of solutions of random satisfiability formulas
• The Satisfiability Threshold for $k$-XORSAT, using an alternative proof