EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The real tau‐conjecture is true on average

Irénée Briquel, Peter Bürgisser

Random Structures & Algorithms · 2020-09 · 57 (2) · 279-303

DOI: 10.1002/rsa.20926 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 15.05.2020. Verfasst von Irénée Briquel und 1 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Deutsche Forschungsgemeinschaft, European Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 mkt . This conjecture has a major consequence in complexity theory since it would lead to superpolynomial lower 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 .

Förderung

  • Deutsche Forschungsgemeinschaft
  • European Research Council

Zitieren

APA

Briquel, I., & Bürgisser, P. (2020). The real tau‐conjecture is true on average. Random Structures & Algorithms, 57(2), 279-303. https://doi.org/10.1002/rsa.20926

Vancouver

Briquel I, Bürgisser P. The real tau‐conjecture is true on average. Random Structures & Algorithms. 2020;57(2):279-303. doi:10.1002/rsa.20926

BibTeX
@article{Briquel2020,
  author = {Briquel, Irénée and Bürgisser, Peter},
  title = {The real tau‐conjecture is true on average},
  journal = {Random Structures & Algorithms},
  year = {2020},
  volume = {57},
  number = {2},
  pages = {279--303},
  doi = {10.1002/rsa.20926}
}
Kostenlos starten →