direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

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)$.
Link to publication [1] Link to original publication [2] Download Bibtex entry [3]
------ Links: ------

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.
Copyright TU Berlin 2008