Inhalt des Dokuments
All Publications
Zitatschlüssel | BB-The-Real-Tau-Conjecture-Is-True-On-Average |
---|---|
Autor | Iréné Briquel and Peter Bürgisser |
Jahr | 2020 |
DOI | 10.1002/rsa.20926 |
Journal | Random Structures & Algortihms |
Notiz | This is an online version before inclusion in an issue of the journal. |
Zusammenfassung | 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)$. |
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe
Hilfsfunktionen
Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.