SCS Undergraduate Thesis Topics

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.