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] (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 characterize a related class VW[F]$, in terms of permanents, where we consider an exponential sum of algebraic formulas instead of circuits. We show that when we sum over cycle covers that have one long cycle and all other cycles have constant length, then the resulting family of polynomials is complete for VW[F] on certain types of graphs.

One of the most important open problems in algebraic complexity theory is to design an efficient deterministic algorithm for computing the rank of linear matrices (usually stated over a set of commutative variables). At present, we know efficient deterministic algorithms when the variables do not commute, and when the variables partially commute (in a limited sense). Also, for the commutative case, a fully polynomial-time rank approximation is known. In this study, we focus on the approximation problem further. We provide a gentle outline of the known algorithms and then highlight some aspects of an approximation algorithm in the setting of partially commutative variables.