A Unified Approach to Lower Bounds and Derandomization
COM1 Level 3
MR1, COM1-03-19
Abstract
Given a univariate polynomial f of degree d (over complex numbers), what is the 'minimal' way to express it as a sum-of-squares of univariates, i.e., for some s?
What is the number of real roots of a given f as a sum-of-squares? It turns out that these two questions are very much related, and a good enough understanding of these questions will lead to completely solving the algebraic version of the holy grail of theoretical computer science: P != NP; also known as Valiant's VP != VNP. We will discuss some of the explicit connections.
On the other hand, a sibling problem to this, known as Polynomial Identity Testing (PIT), is to check non-zeroness of a given (multivariate) polynomial f. Though a very straightforward randomized algorithm exists for PIT, a deterministic polynomial-time solution has long been desired, but not yet achieved. There have been significant efforts to design efficient deterministic PIT, assuming different restricted structures on f. We will discuss some of them.
We will also briefly talk about how algebraic approximations are relevant and related to all the questions above. This dates back to earlier works by Strassen's work on a faster matrix multiplication algorithm. We will see some of the recent advancements in this area, and their intimate connections with the classical P != NP question.
Bio
Pranjal Dutta (https://sites.google.com/view/pduttashomepage) is currently a Postdoc at the School of Computing, NUS, in the group of Prof. Divesh Aggarwal. His broad research area is Complexity theory. He finished his PhD in Computer Science (2018-2022), from Chennai Mathematical Institute (CMI), under the guidance of Prof. Nitin Saxena (IIT Kanpur). He is the winner of the ACM India Doctoral Dissertation Award 2023. During his PhD, he was a recipient of the Google PhD Fellowship (2018-2022). He obtained his bachelor's in Mathematics and Computer science (2013-2016) and master's in Computer science (2016-2018) both from CMI.