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)

 

This talk is based on joint work with Markus Blaser (University of Saarland), Pranjal Dutta (NUS) and Saswata Mukherjee (NUS) [ICALP 2024], link: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.24