Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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