Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces Academic Article

abstract

• 2017 Elsevier Inc. Given any complex Laurent polynomial f, Amoeba(f) is the image of its complex zero set under the coordinate-wise log absolute value map. We discuss an efficiently constructible polyhedral approximation, ArchTrop(f), of 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 ArchTrop(f) is doable in polynomial-time, for any fixed dimension, unlike the corresponding problem for Amoeba(f), which is NP-hard already in one variable. ArchTrop(f) can thus serve as a canonical low order approximation to start a higher order iterative polynomial system solving algorithm, e.g., homotopy continuation.

authors

• Rojas, Joseph

published proceedings

• JOURNAL OF COMPLEXITY

author list (cited authors)

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

citation count

• 12

complete list of authors

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

publication date

• January 2018

publisher

• Elsevier  Publisher

published in

• Journal of Complexity  Journal

keywords

• Amoeba
• Archimedean
• Complexity
• Hausdorff Distance
• Tropical Variety

Digital Object Identifier (DOI)

• 10.1016/j.jco.2017.11.008

start page

• 45

end page

• 65

volume

• 46

URL

• http://dx.doi.org/10.1016/j.jco.2017.11.008