Chapter 4 notes


Chapter 4 exercises


§4.5: Highlight: LMN’s work on constant-depth circuits

Having derived strong results about the Fourier spectrum of small DNFs and CNFs, we will now extend to the case of constant-depth circuits. We begin by describing how Håstad applied his Switching Lemma to constant-depth circuits. We then describe some Fourier-theoretic consequences coming from a very early (1989) work in 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.2: Tribes

In this section we study the tribes DNF formulas, which serve as an important examples and counterexamples in analysis of boolean functions. Perhaps the most notable feature of the tribes function is that (for a suitable choice of parameters) it is essentially unbiased and yet all of its influences are quite tiny.


§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:


Chapter 4: DNF formulas and small-depth circuits

In this chapter we investigate boolean functions representable by small DNF formulas and constant-depth circuits; these are significant generalizations of decision trees. Besides being natural from a computational point of view, these representation classes are close to the limit of what complexity theorists can “understand” (e.g., prove explicit lower bounds for). One reason [...]