Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MALLIAVIN CALCULUS:
Reports tagged with Malliavin calculus:
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