Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > STEIN:
Reports tagged with Stein:
TR10-179 | 18th November 2010
Gregory Valiant, Paul Valiant

#### A CLT and tight lower bounds for estimating entropy

Revisions: 1

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 >>>

TR13-173 | 28th November 2013
Anindya De, Rocco Servedio

#### Efficient deterministic approximate counting for low degree polynomial threshold functions

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 >>>

ISSN 1433-8092 | Imprint