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

Emmanuel Abbe, Katherine Edwards

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 $…