Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-387-92
Probabilistic Spaces of Boolean Functions of a Given Complexity: Generalities and Random $k$-SAT Coefficients
Authors: Friedman, Joel
Date:July 1992
Pages:27
Download Formats:
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.