The real tau‐conjecture is true on average

dc.contributor.authorBriquel, Irénée
dc.contributor.authorBürgisser, Peter
dc.date.accessioned2020-12-08T08:56:51Z
dc.date.available2020-12-08T08:56:51Z
dc.date.issued2020-05-15
dc.date.updated2020-11-02T21:31:13Z
dc.description.abstractKoiran'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 𝒪(mk2t).en
dc.description.sponsorshipEC/H2020/787840/EU/Complexity and Condition in Algebra and Numerics/COCANen
dc.description.sponsorshipTU Berlin, Open-Access-Mittel – 2020de
dc.identifier.eissn1098-2418
dc.identifier.issn1042-9832
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/12133
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-11007
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc512 Algebrade
dc.subject.othercomplexity theoryen
dc.subject.otherdepth four arithmetic circuitsen
dc.subject.otherDescartes ruleen
dc.subject.othersparsityen
dc.subject.othertau‐conjectureen
dc.subject.otherzeros of random polynomialsen
dc.titleThe real tau‐conjecture is true on averageen
dc.typeArticleen
dc.type.versionpublishedVersionen
dcterms.bibliographicCitation.doi10.1002/rsa.20926en
dcterms.bibliographicCitation.issue2en
dcterms.bibliographicCitation.journaltitleRandom Structures & Algorithmsen
dcterms.bibliographicCitation.originalpublishernameWileyen
dcterms.bibliographicCitation.originalpublisherplaceNew Yorken
dcterms.bibliographicCitation.pageend303en
dcterms.bibliographicCitation.pagestart279en
dcterms.bibliographicCitation.volume57en
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Algorithmische Algebrade
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.groupFG Algorithmische Algebrade
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
RSA_RSA20926.pdf
Size:
541.35 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.9 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections