2013/12/23 by E. Kathleen Anthony, Anthony, Eleanor, Sheridan Grant +5
Computer Science · Mathematics · #Algebraic Geometry (math.AG) #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Methods and Algorithms #Optimization and Control (math.OC) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1312.6547
openalex publication_date 2013/12/23 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
We derive efficient algorithms for coarse approximation of algebraic\nhypersurfaces, useful for estimating the distance between an input polynomial\nzero set and a given query point. Our methods work best on sparse polynomials\nof high degree (in any number of variables) but are nevertheless completely\ngeneral. The underlying ideas, which we take the time to describe in an\nelementary way, come from tropical geometry. We thus reduce a hard algebraic\nproblem to high-precision linear optimization, proving new upper and lower\ncomplexity estimates along the way.\n