DNF « Analysis of Boolean Functions

§4.4: Håstad’s Switching Lemma and the spectrum of DNFs

Let’s further investigate how random restrictions can simplify DNF formulas.

[...]

§4.3: Random restrictions

In this section we describe the method of applying random restrictions. This is a very “Fourier-friendly” way of simplifying a boolean function.

[...]

§4.1: DNF formulas

Perhaps the commonest way of representing a boolean function $f : \{0,1\}^n \to \{0,1\}$ is by a DNF formula:

[...]