Alladi Ramakrishnan Hall

On the Composition of the Complexity Measures of Boolean Functions

Chandrima Kayal

IMSc

We can compose two Boolean functions f and g to obtain a new function (f o g), but what happens to the complexity measures? Can we express the complexity of the composed function in terms of the smaller functions ( f and g) ? Precisely, the question is if the following holds:
M(f o g) = Theta(M(f). M(g)) for some particular complexity measure (of Boolean function ) M.
This is one of the fundamental questions in the area of Analysis of Boolean functions. Following a long line of work there are two big open problems in this area:
1. Does approximate degree compose?
2. Does randomized query complexity compose?

Although these two measures are standard and well-studied, still it is not known if they behave nicely under composition or not. In these studies, we have explored two different directions and generalized the existing results, which gave an affirmative answer to both the problems for larger classes of functions. In this talk, we will describe some of the recent results and the related open problems.

Talk is based on the two following works:
1. On the Composition of Randomized Query Complexity and Approximate Degree.
joint work with Sourav Chakraborty, Rajat Mittal, Manaswi Parashaar, Swagato Sanyal, and Nitin Saurabh.
2. Approximate degree composition for recursive functions.
joint work with Sourav Chakraborty, Rajat Mittal, Manaswi Parashaar, and Nitin Saurabh.