Tropical Varieties for Exponential Sums

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 ${\mathbb{R}}^n$. In particular, we give an explicit upper bound on the Hausdorff distance: $\Delta(R,T) =O\left(t^{3.5}/\delta\right)$,where$t$and$\delta$ 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 $\mathbb{R}$, whereas membership and distance queries for our polyhedral approximation $T$ can be decided in polynomial-time for any fixed $n$.