Formula complexity of polynomials and lower bounds

Algebraic Complexity Theory and Lower Bounds.

In this project, we study the computation of multivariate polynomials along two axes.
1. Lower bounds on the computation of polynomials.
2. Evaluations of polynomials and counting.

Proving lower bounds on the computation of polynomials is a fundamental question in theoretical computer science. The famous P vs. NP question has an algebraic variant called the VP vs. VNP question. The exact question is: Are there explicit polynomials that cannot be computed efficiently? In a recent work [LST2021], we made substantial progress towards answering this question. We would like to push our techniques further to obtain stronger results. This is one of the main axes I plan to explore in this project. Specifically, we believe that the current lower bound technique can be thought of as a special instance of “flattenings”, which arise in quantum computation. The ‘flattenings’ are used to prove lower bounds on tensors. The project will explore possibilities to combine the methods from Quantum Computation with our lower bound methods.

Another set of equally intriguing questions about polynomials arises from evaluating them or approximating them. In the last decade, we have understood the close connections between the efficient evaluation of polynomials and better- than-brute-force algorithms for NP-complete and #P-Complete problems. In the past, I have tried to understand Boolean complexity classes inside P using counting problems arising from word problems. I would like to explore the landscape of counting problems arising from non-commutative polynomial evaluations. Non-commutative polynomials are generalizations of word problems. This is the second axis of inquiry in this project.