Valiant's famous VP vs. VNP conjecture states that the symbolic permanent polynomial does not have polynomial-size algebraic circuits. However, the best upper bound on the size of the circuits computing the permanent is exponential. Informally, VNP is an exponential sum of VP-circuits. In this paper we study whether, in general, exponential sums of algebraic circuits require exponential-size algebraic circuits. We show that the famous Shub-Smale tau-conjecture indeed implies such an exponential lower bound for an exponential sum. Our main tools come from parameterized complexity. Along the way, we also prove an exponential fpt (fixed-parameter tractable) lower bound for the parameterized algebraic complexity class VW[P], weighted sum circuits (constant-free, unbounded degree), assuming the same conjecture. VW[P] can be thought of as the weighted sums of (unbounded-degree) circuits, where only +1/-1 constants are cost-free. To the best of our knowledge, this is the first time the Shub-Smale tau-conjecture has been applied to prove explicit exponential lower bounds. Furthermore, we prove that when this class is fpt, then a variant of the counting hierarchy, namely the linear counting hierarchy collapses. Moreover, if a certain type of parameterized exponential sums is fpt, then integers, as well as polynomials with coefficients being definable in the linear counting hierarchy have subpolynomial tau-complexity. Finally, we showed a completeness result on a subclass VW[F] (weighted sum of formulas)
Short Bio:
Somnath completed his Bachelors and Masters from the Chennai Mathematical Institute and is on his way to the University of Toronto for his PhD. His current research interests are in algorithms and complexity with a focus on problems with an algebraic flavor, including algebraic complexity, algebraic algorithms, pseudorandomness, algebraic proof complexity and error correcting codes.
