A Wronskian approach to the real -conjecture

DOI10.1016/J.JSC.2014.09.036zbMATH Open1302.68331arXiv1205.1015OpenAlexW2073036037WikidataQ123309854 ScholiaQ123309854MaRDI QIDQ480686FDOQ480686

Pascal Koiran, Sébastien Tavenas, Natacha Portier

Publication date: 9 December 2014

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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

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

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

zbMATH Keywords

real algebraic geometryreal \(\tau\)-conjecturesparse polynomials

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Real algebraic and real-analytic geometry (14P99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Completeness and reduction in algebraic complexity theory
• Counting real connected components of trinomial curve intersections and \(m\)-nomial hypersurfaces
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Title not available (Why is that?)
• On circuit lower bounds from derandomization
• Title not available (Why is that?)
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• The number of roots of a lacunary bivariate polynomial on a line
• The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
• Simple exponential estimate for the number of real zeros of complete abelian integrals
• The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent
• Progress on Polynomial Identity Testing - II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational Complexity of Sparse Rational Interpolation

Cited In (12)

• 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
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• 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
• A complexity chasm for solving univariate sparse polynomial equations over \(p\)-adic fields
• Intersection multiplicity of a sparse curve and a low-degree curve
• An explicit solution to Post's problem over the reals

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)