A \(\tau \)-conjecture for Newton polygons

DOI10.1007/s10208-014-9216-xzbMath1327.68135arXiv1308.2286OpenAlexW2111659436WikidataQ123146204 ScholiaQ123146204MaRDI QIDQ2340507

Natacha Portier, Pascal Koiran, Sébastien Tavenas, Steéphan Thomassé

Publication date: 20 April 2015

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Newton polygonconvex hullarithmetic circuit complexity\(\tau\)-conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)

Related Items (6)

Log-Concavity and Lower Bounds for Arithmetic Circuits ⋮ Shadows of Newton polytopes ⋮ Tropical combinatorial Nullstellensatz and sparse polynomials ⋮ On the distribution of runners on a circle ⋮ Intersection multiplicity of a sparse curve and a low-degree curve ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arithmetic circuits: the chasm at depth four gets wider
• A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
• Large convexly independent subsets of Minkowski sums
• On defining integers and proving arithmetic circuit lower bounds
• The convex dimension of a graph
• Convexly independent subsets of the Minkowski sum of planar point sets
• Completeness and reduction in algebraic complexity theory
• Mathematical problems for the next century
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Polynomial Equations and Convex Polytopes
• Arithmetic Circuits: A Chasm at Depth 3
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Partial Derivatives in Arithmetic Complexity and Beyond
• Arithmetic Circuits: A survey of recent results and open questions
• On the Number of Additions to Compute Specific Polynomials
• Sums of Like Powers of Multivariate Linear Forms
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Absolute irreducibility of polynomials via Newton polytopes

This page was built for publication: A \(\tau \)-conjecture for Newton polygons