Tropical varieties for exponential sums
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
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.