| Title | : | On the composition of approximate degree |
| Speaker | : | Nitin Saurabh (IIT Hyderabad) |
| Details | : | Thu, 4 Dec, 2025 2:30 PM @ SSB 334 |
| Abstract: | : | A polynomial p(x) is said to approximate a Boolean function f:{0,1}^n -> {0,1} if |f(x)-p(x)| <= 1/3 for all x in {0,1}^n. The approximate degree of f, denoted adeg(f), is defined to be the minimal degree of an approximating polynomial for f. It was introduced roughly 30 years back in a seminal work of Nisan and Szegedy (Computational Complexity 1994). Since then it has become a powerful and versatile tool in theoretical computer science finding spectacular applications in circuit complexity, quantum query complexity, communication complexity, computational learning, and differential privacy, to name a few. In a beautiful and significant work, Sherstov (Theory of Computing 2013) showed that adeg(f o g) = O(adeg(f)adeg(g)), where f o g is obtained by substituting variables of f by independent copies of g. The approximate degree composition problem posits that this upper bound is tight. That is, adeg(f o g) = Omega(adeg(f) adeg(g)) for all f and g. I will present a recent work of mine (along with my collaborators) on this problem. Furthermore, I will also present an overview of my research work and future plans. |
