FG Algorithmische Algebra

1 Items

Recent Submissions
The real tau‐conjecture is true on average

Briquel, Irénée ; Bürgisser, Peter (2020-05-15)

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 con...