The real tau-conjecture is true on average

Abstract

Koiran's real $\tau$-conjecture claims that the number of real zeros of a structured polynomial given as a sum of $m$ products of $k$ real sparse polynomials, each with at most $t$ monomials, is bounded by a polynomial in $m,k,t$. This conjecture has a major consequence in complexity theory since it would lead to superpolynomial bounds for the arithmetic circuit size of the permanent. We confirm the conjecture in a probabilistic sense by proving that if the coefficients involved in the description of $f$ are independent standard Gaussian random variables, then the expected number of real zeros of $f$ is $O(m{k}^{2}t)$.

The first version had an error in the proof of the main theorem, which is now corrected. We also simplified the statement of the Rice inequality (Theorem 3.2), which led to some simplifications

References in corpus (1)

• On the Number of Real Zeros of Random Fewnomials

Cited by in corpus (1)

• Real zeros of mixed random fewnomial systems