The real tau‐conjecture is true on average. Issue 2 (15th May 2020)

• Record Type: Journal Article
• Authors: Briquel, Irénée; Bürgisser, Peter
• Is Part Of: Random structures & algorithms. Volume 57:Issue 2(2020)
• Page Start: 279
• Page End: 303
• Publication Date: 2020-05-15
• Subjects: complexity theory -- depth four arithmetic circuits -- Descartes rule -- sparsity -- tau‐conjecture -- zeros of random polynomials; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20926
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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 𝒪 ( m k 2 t ) .