Boolean functions capture various problems and situations arising in computer science and other areas. In this synopsis, we study boolean functions using two complexity 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 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 Fourier rank in terms of Fourier sparsity, weight, Fourier max-entropy and Fourier max-rank entropy. We will also exhibit functions which match these bounds.
