A Wronskian approach to the real -conjecture
From MaRDI portal
Abstract: According to the real au-conjecture, the number of real roots of a sum of products of sparse polynomials should be polynomially bounded in the size of such an expression. It is known that this conjecture implies a superpolynomial lower bound on the arithmetic circuit complexity of the permanent. In this paper, we use the Wronksian determinant to give an upper bound on the number of real roots of sums of products of sparse polynomials. The proof technique is quite versatile; it can in particular be applied to some sparse geometric problems that do not originate from arithmetic circuit complexity. The paper should therefore be of interest to researchers from these two communities (complexity theory and sparse polynomial systems).
Recommendations
- The real tau-conjecture is true on average
- The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent
- On the real \(\tau\)-conjecture and the distribution of complex roots
- A \(\tau \)-conjecture for Newton polygons
- Randomization, sums of squares, near-circuits, and faster real root counting
Cites work
- scientific article; zbMATH DE number 3940124 (Why is no real title available?)
- scientific article; zbMATH DE number 3744549 (Why is no real title available?)
- scientific article; zbMATH DE number 52070 (Why is no real title available?)
- scientific article; zbMATH DE number 3485662 (Why is no real title available?)
- scientific article; zbMATH DE number 3494742 (Why is no real title available?)
- scientific article; zbMATH DE number 503193 (Why is no real title available?)
- Completeness and reduction in algebraic complexity theory
- Computational Complexity of Sparse Rational Interpolation
- Counting real connected components of trinomial curve intersections and \(m\)-nomial hypersurfaces
- Derandomizing polynomial identity tests means proving circuit lower bounds
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- On circuit lower bounds from derandomization
- On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
- Progress on polynomial identity testing
- Simple exponential estimate for the number of real zeros of complete abelian integrals
- The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
- The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent
- The number of roots of a lacunary bivariate polynomial on a line
Cited in
(15)- Intersection multiplicity of a sparse curve and a low-degree curve
- Real zeros of mixed random fewnomial systems
- Computing the multilinear factors of lacunary polynomials without heights
- On the intersection of a sparse curve and a low-degree curve: a polynomial version of the lost theorem
- Lower bounds for sums of powers of low degree univariates
- Tropical combinatorial Nullstellensatz and sparse polynomials
- The real tau-conjecture is true on average
- On the number of real zeros of random fewnomials
- Geometry of the signed support of a multivariate polynomial and Descartes' rule of signs
- A sharp bound on the number of real intersection points of a sparse plane curve with a line
- An explicit solution to Post's problem over the reals
- The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent
- On the real \(\tau\)-conjecture and the distribution of complex roots
- A complexity chasm for solving univariate sparse polynomial equations over \(p\)-adic fields
- Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
This page was built for publication: A Wronskian approach to the real \(\tau\)-conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q480686)
