HYDERABAD EECS THEORY SEMINARS (HyTS)

Talk by Dr. Nitin Saurabh on 20 August, 2025

  • Physical Venue: Room EE004 (ground floor of EECS building).

  • Join Online: Google Meet Link

  • Date/Time: 20 Aug (Wed), 4.00pm

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!

Upcoming talks by Karthik PN and Rajesh Kannan on Sept 10, 2025

Time: 2-5.30pm
Details will be put up soon!