An (n, k)-Poisson Multinomial Distribution (PMD) is a random variable of the form X = ∑i=1n Xi, where the Xi’s are independent random vectors supported on the set of standard basis vectors in k. In this paper, we obtain a refined structural understanding of PMDs by analyzing their Fourier transform. As our core structural result, we prove that the Fourier transform of PMDs is approximately sparse, i.e., its L1-norm is small outside a small set. By building on this result, we obtain the following applications: