The real tau‐conjecture is true on average

DOI10.1002/rsa.20926zbMath1493.68138arXiv1806.00417OpenAlexW3024816162WikidataQ123287981 ScholiaQ123287981MaRDI QIDQ5136915

Irenée Briquel, Peter Bürgisser

Publication date: 30 November 2020

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1806.00417

zbMATH Keywords

complexity theorysparsityzeros of random polynomialsDescartes ruledepth-four arithmetic circuitstau-conjecture

Mathematics Subject Classification ID

Random fields (60G60) Symbolic computation and algebraic computation (68W30) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (4)

Real zeros of mixed random fewnomial systems ⋮ New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023 ⋮ On the Number of Real Zeros of Random Fewnomials ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

This page was built for publication: The real tau‐conjecture is true on average