Leitung

Prof. Dr. Peter Bürgisser

Anschrift
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Büro
Raum MA 317 (3. OG)
Institut für Mathematik

Sekretariat
Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771

eMail
pbuerg@math.tu-berlin.de
contact form

Telefon
+49 (0)30 314 - 75902

Faxgerät
+49 (0)30 314 - 25839

Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.

The real tau-conjecture is true on average
Citation key	BB-The-Real-Tau-Conjecture-Is-True-On-Average
Author	Iréné Briquel and Peter Bürgisser
Year	2020
DOI	10.1002/rsa.20926
Journal	Random Structures & Algortihms
Note	This is an online version before inclusion in an issue of the journal.
Abstract	Koiran's real τ-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(mk^2t)$.