Probabilistic Spaces of Boolean Functions of a Given Complexity: Generalities and Random $k$-SAT Coefficients
Report ID: TR-387-92Author: Friedman, Joel
Date: 1992-07-00
Pages: 28
Download Formats: |PDF|
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.