Tropical varieties for exponential sums Academic Article uri icon

abstract

  • © 2019, Springer-Verlag GmbH Germany, part of Springer Nature. We study the complexity of approximating complex zero sets of certain n-variate exponential sums. We show that the real part, R, of such a zero set can be approximated by the (n- 1) -dimensional skeleton, T, of a polyhedral subdivision of Rn. In particular, we give an explicit upper bound on the Hausdorff distance: Δ (R, T) = O(t3.5/ δ) , where t and δ are respectively the number of terms and the minimal spacing of the frequencies of g. On the side of computational complexity, we show that even the n= 2 case of the membership problem for R is undecidable in the Blum-Shub-Smale model over R, whereas membership and distance queries for our polyhedral approximation T can be decided in polynomial-time for any fixed n.

altmetric score

  • 0.75

author list (cited authors)

  • Ergür, A. A., Paouris, G., & Rojas, J. M.

citation count

  • 0

publication date

  • January 2019