Gregory Valiant, Paul Valiant

We prove two new multivariate central limit theorems; the first relates the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance matric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central ... more >>>

Anindya De, Rocco Servedio

We give a deterministic algorithm for

approximately counting satisfying assignments of a degree-$d$ polynomial threshold function

(PTF).

Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$

and a parameter $\epsilon > 0$, our algorithm approximates

$

\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]

$

to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ...
more >>>