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 for this is that functions in these classes have strong Fourier concentration properties.