Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

In this paper, we prove the first super-polynomial and, in fact, exponential lower bound for the model of sum of read-once oblivious algebraic branching programs (ROABPs). In particular, we give an explicit polynomial such that any sum of ROABPs
(equivalently, sum of *ordered* set-multilinear branching programs, each with a ... more >>>