Decision Tree and Fourier Complexity of Boolean Functions
In this work we collect various combinatorial properties (i.e. communication and decision tree complexity) of symmetric parity (XOR) and
AND functions. We also include various Fourier analytical properties of these same functions, such as the Fourier L1 norm, degree and
approximate degree, and the monomial complexity. These Fourier analytical properties are often strongly related to various upper and
lower bounds in learning theory, circuit complexity, and communication complexity. Furthermore, we study the relationships between
different notions of Decision Tree complexity, and are able to show that the depth of regular decision trees is at most the product of the
depths of the AND and OR decision trees. Finally, we consider the relationship between Fourier complexity and Decision Tree complexity
and show that the total influence can be bounded by decision tree depth.