Exponential lower bound via exponential sums

Markus Bläser, Somnath Bhattacharjee, Pranjal Dutta, Saswata Mukherjee · 2026

Read Exponential lower bound via exponential sums by Markus Bläser, Somnath Bhattacharjee, Pranjal Dutta, Saswata Mukherjee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-00387.txt.

Introduction

Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee study whether adding up very many small algebraic circuits can force the total size to explode. The question echoes a famous open conjecture about the permanent polynomial. Their 2026 paper, an extended version of a 2024 conference paper, ties the question to the Shub-Smale tau conjecture, a deep claim about how hard it is to write down integers.

Assuming that conjecture, the team proves an exponential lower bound for such sums. Their tools come from parameterized complexity, and they also prove a matching lower bound for a weighted parameterized class. Further results link that class to a collapse of a counting hierarchy, and a related class is described through permanents.

Catalog record

CREATORMarkus Bläser, Somnath Bhattacharjee, Pranjal Dutta, Saswata Mukherjee
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-00387

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exponential lower bound via exponential sums Thanks: This is an extended version of the ICALP 2024 paper [ 3 ] . Markus Bläser, Somnath Bhattacharjee, Pranjal Dutta, Saswata Mukherjee Abstract Valiant’s famous 𝖵𝖯 \mathsf{VP} vs. 𝖵𝖭𝖯 \mathsf{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, 𝖵𝖭𝖯 \mathsf{VNP} is an exponential sum of 𝖵𝖯 \mathsf{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 𝖵𝖶 nb 0 ​ [ 𝖯 ] \mathsf{VW}_{\textup{nb}}^{0}[\mathsf{P}] , assuming the same conjecture. 𝖵𝖶 nb 0 ​ [ 𝖯 ] \mathsf{VW}_{\textup{nb}}^{0}[\mathsf{P}] can be thought of as the weighted sums of (unbounded-degree) circuits, where only ± 1 \pm 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 𝖵𝖶 ⁡ [ 𝖥 ] \mathsf{VW}[\mathsf{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 𝖵𝖶 ⁡ [ 𝖥 ] \mathsf{VW}[\mathsf{F}] on certain types of graphs. 1 Introduction Valiant [ 27 ] proposed an algebraic version of the \mathsf{P} versus \mathsf{NP} question and defined the class \mathsf{VP} , the algebraic analogue of \mathsf{P} , which contains polynomial families computable by polynomial sized algebraic circuits. An algebraic circuit (or, arithmetic circuit) C is a directed acyclic graph such that 1. every node has either in-degree ( fan-in ) 0 (the input gates ) or 2 (the computational gates ), 2. every input gate is labeled by elements from a field \mathbb{K} or variables from \mathbf{X}=\{X_{1},\cdots,X_{n}\} , 3. every computational gate is labeled by either + (addition gate) or \times (multiplication gate), with the obvious syntactic meaning, and 4. there is a unique gate of out-degree 0 , the output gate . Clearly, every gate in a circuit computes a polynomial in \mathbb{K}[\mathbf{X}] . We say that the circuit C computes P(\mathbf{X})\in\mathbb{K}[\mathbf{X}] if the output gate of C computes P(\mathbf{X}) . The size of C , denoted by {\rm size}(C) , is the number of nodes in the circuit. An algebraic circuit is an algebraic formula if every gate in the circuit has out-degree 1 except for the output gate. The class \mathsf{VNP} , the algebraic analogue of \mathsf{NP} , is definable by taking exponential sums of the form f(\mathbf{X})=\sum_{e\in\{0,1\}^{\ell}}g(\mathbf{X},e)\;, (1) where g is computable by a polynomial-size circuit and \ell is polynomial in the number of variables. It is known that one can also replace algebraic circuits by algebraic formulas, and still get the same class \mathsf{VNP} [ 27 , 21 ] . Valiant further proved that the permanent family is complete for \mathsf{VNP} (over fields of characteristic not two). Recall that the permanent of a matrix (X_{i,j}) is defined as \operatorname{per}\mathbf{X}=\sum_{\pi\in S_{n}}X_{1,\pi(1)}\cdots X_{n,\pi(n)}. (2) The famous Valiant’s conjecture \mathsf{VP}\not=\mathsf{VNP} is equivalent to the fact that the permanent does not have polynomial-size circuits. The representation of the permanent in ( 2 ), although it looks very natural, is not optimal . Ryser’s formula [ 23 ] yields an algebraic formula of size O(2^{n}n^{2}) . A formula of similar size was later found by Glynn [ 15 ] . Ryser’s formula is now over sixty years old and has not been improved since. This gives rise to the interesting question whether there is a formula or circuit of subexponential-size (in n ) for the permanent? More generally, we can now ask the following question. Question 1.1 . Is an exponential sum f (as in Eq. ( 1 )) always computable by an algebraic circuit or formulas of size subexponential in \ell , that is, size 2^{o(\ell)} ? Or are there instances for which exponential-size is necessary? Note that exponential-size being necessary is a much stronger claim than \mathsf{VP}\not=\mathsf{VNP} . It could well be that \mathsf{VP}\not=\mathsf{VNP} but still exponential sums like in ( 1 ) have subexponential size circuits! In this paper, we shed some light on the question what happens if exponential sums would always have subexponential size circuits. Question 1.1 serves as a driving force between the famous Shub-Smale \tau -conjecture [ 24 ] and exponential lower bounds on exponential sums. The \tau -complexity \tau(f) of an integer polynomial is the size of a smallest division-free circuit that computes f starting from the constants \pm 1 . The \tau -conjecture states that the number of integer zeroes of f is polynomially bounded in \tau(f) , see [ 24 ] . [ 24 ] shows that the \tau -conjecture implies \mathsf{P}_{\mathbb{C}}\neq\mathsf{NP}_{\mathbb{C}} , in the Blum–Shub–Smale (BSS) model of computation over the complex numbers [ 6 , 5 ] . Super-polynomial lower bounds assuming the \tau -conjecture. Bürgisser [ 9 ] connected the \tau -complexity of the permanent to various other conjectures. He showed that the \tau -conjecture implies a superpolynomial lower bound on \tau(\operatorname{per}_{n}) , implying the constant-free version of \mathsf{VP}\neq\mathsf{VNP} , namely \mathsf{VP}^{0}\neq\mathsf{VNP}^{0} ; for definitions, see Section 2.1 . The proof strategy of [ 9 ] is as follows: assume \tau(\operatorname{per}_{n})={\rm poly}(n) , and conclude a complexity-theoretic ‘collapse’ that the counting hierarchy \mathsf{CH} (for a definition, see Section 3 ) is in \mathsf{P}/{\rm poly} . Consider the Pochhammer–Wilkinson polynomial f_{n}(x):=\prod_{i=1}^{n}(x-i) , and construct a unique O(\log n) -variate multilinear polynomial B_{n} such that under a ‘suitable’ substitution, one gets back f_{n} . The coefficients of f_{n} as well as B_{n} , are efficiently computable (since \mathsf{CH}\subseteq\mathsf{P}/{\rm poly} ), implying B_{n}\in\mathsf{VNP}^{0} . An inspection of Valiant’s completeness result reveals that if B_{n}\in\mathsf{VNP}^{0} , then there is a polynomially bounded sequence p(n) such that \tau(2^{p(n)}B_{n})={\rm poly}(\log n) , which implies \tau(2^{p(n)}f_{n})={\rm poly}(\log n) , contradicting the \tau -conjecture. In [ 9 ] , the superpolynomial lower bound on \tau(\operatorname{per}_{n}) was also implied by any of the quantities \tau(n!) , \tau(\sum_{k=0}^{n}\frac{1}{k!}T^{k}) , or \tau(\sum_{k=0}^{n}k^{r}T^{k}) (for any fixed negative integer r ) not being poly-logarithmically bounded as a function of n . Here, we remark that the separation proof of \mathsf{VP}^{0} and \mathsf{VNP}^{0} , even assuming strong bounds on the \tau -conjecture, is merely superpolynomial : we do not get the (possibly) desirable exponential separation between \mathsf{VP}^{0} and \mathsf{VNP}^{0} . This leads to the following question. Question 1.2 . Does the \tau -conjecture imply exponential algebraic lower bounds? Here, we mention that there are variants of the \tau -conjecture, e.g.,

Read the complete text