Metric Estimates and Membership Complexity for Archimedean Amoebae and Tropical Hypersurfaces Institutional Repository Document uri icon


  • Given any complex Laurent polynomial $f$, $mathrm{Amoeba}(f)$ is the image of its complex zero set under the coordinate-wise log absolute value map. We give an efficiently constructible polyhedral approximation, $mathrm{ArchtTrop}(f)$, of $mathrm{Amoeba}(f)$, and derive explicit upper and lower bounds, solely as a function of the number of monomial terms of $f$, for the Hausdorff distance between these two sets. We also show that deciding whether a given point lies in $mathrm{ArchTrop}(f)$ is doable in polynomial-time, for any fixed dimension, unlike the corresponding problem for $mathrm{Amoeba}(f)$, which is $mathbf{NP}$-hard already in one variable. $mathrm{ArchTrop}(f)$ can thus serve as a canonical low order approximation to start any higher order iterative polynomial system solving algorithm, such as homotopy continuation. $mathrm{ArchTrop}(f)$ also provides an Archimedean analogue of Kapranov's Non-Archimedean Amoeba Theorem and a higher-dimensional extension of earlier estimates of Mikhalkin and Ostrowski.

author list (cited authors)

  • Avendano, M., Kogan, R., Nisse, M., & Rojas, J. M.

complete list of authors

  • Avendano, Martin||Kogan, Roman||Nisse, Mounir||Rojas, J Maurice

Book Title

  • arXiv

publication date

  • July 2013