Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces

DOI10.1016/j.jco.2017.11.008zbMath1420.14135arXiv1307.3681OpenAlexW2962767068MaRDI QIDQ1745633

Roman Kogan, J. Maurice Rojas, Mounir Nisse, Martín Avendano

Publication date: 18 April 2018

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

complexityHausdorff distancetropical varietyamoebaArchimedean

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) (n)-dimensional polytopes (52B11) Computational aspects of algebraic surfaces (14Q10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computation over the reals, computable analysis (03D78)

Related Items

Degenerations of amoebae and Berkovich spaces, Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields, A survey on computational aspects of polynomial amoebas, The Phaseless Rank of a Matrix, Spectral inequalities for nonnegative tensors and their tropical analogues, Lopsided approximation of amoebas, Tropical totally positive matrices, Correction to: ``Tropical varieties for exponential sums, Tropical varieties for exponential sums

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Amoebas of genus at most one
• Triangulations. Structures for algorithms and applications
• New NP-hard and NP-complete polynomial and integer divisibility problems
• The complexity of elementary algebra and geometry
• The number of roots of a system of equations
• Amoebas, Monge-Ampère measures, and triangulations of the Newton polytope
• Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots
• Decomposition into pairs-of-pants for complex algebraic hypersurfaces
• A nullstellensatz for amoebas
• Recherches sur la méthode de Graeffe et les zéros des polynômes et des séries de Laurent
• Addition à notre memoire: Recherches sur la méthode de Graeffe et les zéros des polynômes et des séries de Laurent. (Acta mathematica 72, 1940/41.)
• An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers. II
• Faster real feasibility via circuit discriminants
• Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond
• Tropical and Idempotent Mathematics
• Non-archimedean amoebas and tropical varieties
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Lectures on Polytopes
• Enumerative tropical algebraic geometry in ℝ²
• Lopsided approximation of amoebas
• New Multiplier Sequences via Discriminant Amoebae
• Polynomial-Time Amoeba Neighborhood Membership and Faster Localized Solving
• Computational Complexity
• On the Computational Complexity of Algorithms
• The On-Line Encyclopedia of Integer Sequences
• Computing Amoebas
• Approximating amoebas and coamoebas by sums of squares
• Decision procedures for real and p‐adic fields
• The Logarithmic Limit-Set of an Algebraic Variety
• Valued Fields
• Tropical and Non-Archimedean Geometry
• Tropical algebraic geometry
• Idempotent functional analysis: An algebraic approach