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

preprint2015arXivOpen access

Abstract

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

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.