Title:On the Composition of the Complexity Measures of Boolean Functions
Speaker: Chandrima Kayal (IMSc Chennai)
Details :Tue, Sep 10, 2024 4:00 PM, @ Turing Hall (SSB 334)
 
Abstract:We can compose two Boolean functions f and g to obtain a new function (f o g), but what happens to the complexity measures? Do they compose? Precisely composition of complexity measures asks if M(f o g) = Theta(M(f). M(g)) for some particular complexity measure M. For understanding different complexity measures of Boolean functions this question plays a central role. 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 this study, we have explored two different directions and generalized the existing results, which gives an affirmative answer to both 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.