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

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

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

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