Polynomial-Time Amoeba Neighborhood Membership and Faster Localized Solving Institutional Repository Document uri icon


  • We derive efficient algorithms for coarse approximation of algebraic hypersurfaces, useful for estimating the distance between an input polynomial zero set and a given query point. Our methods work best on sparse polynomials of high degree (in any number of variables) but are nevertheless completely general. The underlying ideas, which we take the time to describe in an elementary way, come from tropical geometry. We thus reduce a hard algebraic problem to high-precision linear optimization, proving new upper and lower complexity estimates along the way.

author list (cited authors)

  • Anthony, E., Grant, S., Gritzmann, P., & Rojas, J. M.

complete list of authors

  • Anthony, Eleanor||Grant, Sheridan||Gritzmann, Peter||Rojas, J Maurice

Book Title

  • arXiv

publication date

  • December 2013