Probabilistic Spaces of Boolean Functions of a Given Complexity: Generalities and Random $k$-SAT Coefficients

Abstract:

In this paper we develop an approach to studying probabilistic spaces
of boolean functions, namely recovering exact formulas for the event
probabilities in terms of the moments. While this involves analyzing
a large number of moments, there are situations in which this seems
feasible to do; for the $m$-fold AND of a probability space of
functions, there is a formula involving coefficients with a geometric
intepretation (and which is otherwise quite simple). We investigate
the coefficients involved in the $k$-SAT problem, where we give a
formula for the $1$-SAT coefficients and are able to understand a few
of the $2$-SAT coefficients.