Anindya De, Ilias Diakonikolas, Rocco Servedio

Let $g: \{-1,1\}^k \to \{-1,1\}$ be any Boolean function and $q_1,\dots,q_k$ be any degree-2 polynomials over $\{-1,1\}^n.$ We give a \emph{deterministic} algorithm which, given as input explicit descriptions of $g,q_1,\dots,q_k$ and an accuracy parameter $\eps>0$, approximates \[

\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1] \]

to within an additive $\pm \eps$. For any constant ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates

\[

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

\]

to within an additive $\pm \eps$ in ...
more >>>