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.

published proceedings

  • MATHEMATISCHE ANNALEN

altmetric score

  • 1

author list (cited authors)

  • Erguer, A. A., Paouris, G., & Rojas, J. M.

citation count

  • 2

complete list of authors

  • Erguer, Alperen A||Paouris, Grigoris||Rojas, J Maurice

publication date

  • August 2020