Boolean functions capture various problems and situations arising in computer science and other areas. In this thesis, we study boolean functions using three complexity measures namely Probabilistic degree, decision tree depth and Fourier dimension. The thesis and the talk are organized into three parts one for each of these measures.
In the first part of the talk, we will focus on the Probabilistic degree of OR over Reals. This is based on joint work with Bhandari, Harsha and Srinivasan. In this part, we will look at the construction of a Probabilistic Polynomial for OR over Reals, which improves on the previous best construction due to Toda-Ogiwara and Beigel, Tarui, Reingold and Speilman. We will also look at a lower bound on the Probabilistic degree of OR which matches our upper bound construction in a restricted setting.
In the second part, we will focus on decision trees of Boolean functions after random restrictions.
This is based on joint work with Harsha and Shankar. In this part, we will look at the notion of the criticality of a Boolean function which captures several properties of Boolean functions tightly. In our work, we prove a switching lemma-like statement for Boolean Formulas which settles a conjecture of Rossman.
In the third part, we will look at a bunch of complexity measures which arise out of the Fourier representation of Boolean functions and study the relationship between them. This is based on joint work with Chakraborty, Mande, Mittal, Paraashar and Sanyal. In this part, we will focus on a couple of upper bounds on the Fourier dimension in terms of Fourier sparsity, weight, Fourier max-entropy and Fourier max-rank entropy. We will also exhibit functions which match these bounds.
