English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

An $(n, k)$-Poisson Multinomial Distribution (PMD) is a random variable ofthe form $X = \sum_{i=1}^n X_i$, where the $X_i$'s are independent randomvectors supported on the set of standard basis vectors in $\mathbb{R}^k.$ Inthis paper, we obtain a refined structural understanding of PMDs by analyzingtheir Fourier transform. As our core structural result, we prove that theFourier transform of PMDs is {\em approximately sparse}, i.e., roughlyspeaking, its $L_1$-norm is small outside a small set. By building on thisresult, we obtain the following applications:  {\bf Learning Theory.} We design the first computationally efficient learningalgorithm for PMDs with respect to the total variation distance. Our algorithmlearns an arbitrary $(n, k)$-PMD within variation distance $\epsilon$ using anear-optimal sample size of $\widetilde{O}_k(1/\epsilon^2),$ and runs in time$\widetilde{O}_k(1/\epsilon^2) \cdot \log n.$ Previously, no algorithm with a$\mathrm{poly}(1/\epsilon)$ runtime was known, even for $k=3.$  {\bf Game Theory.} We give the first efficient polynomial-time approximationscheme (EPTAS) for computing Nash equilibria in anonymous games. For normalizedanonymous games with $n$ players and $k$ strategies, our algorithm computes awell-supported $\epsilon$-Nash equilibrium in time $n^{O(k^3)} \cdot(k/\epsilon)^{O(k^3\log(k/\epsilon)/\log\log(k/\epsilon))^{k-1}}.$ The bestprevious algorithm for this problem had running time $n^{(f(k)/\epsilon)^k},$where $f(k) = \Omega(k^{k^2})$, for any $k>2.$  {\bf Statistics.} We prove a multivariate central limit theorem (CLT) thatrelates an arbitrary PMD to a discretized multivariate Gaussian with the samemean and covariance, in total variation distance. Our new CLT strengthens theCLT of Valiant and Valiant by completely removing the dependence on $n$ in theerror bound.

The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications