[...]


[...] [...] Having derived strong results about the Fourier spectrum of small DNFs and CNFs, we will now extend to the case of constantdepth circuits. We begin by describing how Håstad applied his Switching Lemma to constantdepth circuits. We then describe some Fouriertheoretic consequences coming from a very early (1989) work in analysis of boolean functions [...] Let’s further investigate how random restrictions can simplify DNF formulas. [...] In this section we describe the method of applying random restrictions. This is a very “Fourierfriendly” way of simplifying a boolean function. [...] 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. [...] Perhaps the commonest way of representing a boolean function $f : \{0,1\}^n \to \{0,1\}$ is by a DNF formula: [...] In this chapter we investigate boolean functions representable by small DNF formulas and constantdepth 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 [...] 

Copyright © 2015 Ryan O'Donnell  All Rights Reserved 
Recent comments