Title: On the approximate degree composition problem
Abstract: A polynomial \(p(x_1,..,x_n)\) is said to approximate a Boolean function \(f:\{0,1\}^n –> \{0,1\}\) if and only if \(|f(x)-p(x)| \le 1/3\) for all \(x \in \{0,1\}^n\).
That is, \(p\) approximates \(f\) pointwise. The approximate degree of \(f\), denoted \(\mathrm{adeg}(f)\), is defined to be the minimal degree of an approximating polynomial for \(f\).
For any two Boolean functions \(f\) and \(g\), the composed function \(f \circ g\) is defined as, \(f \circ g (x_1,..x_n) = f(g(x_1),…,g(x_n))\), where \(x_i \in \{0,1\}^m\). In a beautiful and significant work Sherstov showed that \(\mathrm{adeg}(f \circ g) = O(\mathrm{adeg}(f)\mathrm{adeg}(g))\). The approximate degree composition problem posits that this upper bound is tight. That is, \(\mathrm{adeg}(f o g) = \Omega(\mathrm{adeg}(f)\mathrm{adeg}(g))\) for all \(f\) and \(g\). This talk will survey the current state of progress and attempts made on this problem.
Bio: Nitin Saurabh is a faculty in CSE dept at IITH. His research interests broadly lie in theoretical computer science, and particularly in computational complexity theory. Recently he has been exploring quantum complexity theory. Long before, he spent his formative years as a PhD student at The Institute of Mathematical Sciences (IMSc), Chennai. Other than work, he enjoys beer, briyani, and running!