We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>>

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit $C$ on $n$ input variables, the procedure outputs a new circuit $C'$ on the same $n$ input variables with the property that ... more >>>