An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing
the polynomial P using only additions and multiplications. It is a syntactic model of …

Koiran showed that if an n-variate polynomial fn of degree d (with d= n O (1)) is computed by
a circuit of size s, then it is also computed by a homogeneous circuit of depth four and of size …

Agrawal and Vinay [2008], Koiran [2012], and Tavenas [2013] have recently shown that an
exp (ω (√ n log n)) lower bound for depth four homogeneous circuits computing the …

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits
computing an explicit polynomial in VP. Our results hold for the iterated matrix multiplication …

We show here a 2^Ω(d⋅\logN) size lower bound for homogeneous depth four arithmetic
formulas over fields of characteristic zero. That is, we give an explicit family of polynomials of …

We consider arithmetic formulas consisting of alternating layers of addition (+) and
multiplication (×) gates such that the fanin of all the gates in any fixed layer is the same …

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by
Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential …

We show that, over \mathbbQ, if an n-variate polynomial of degree d=n^O(1) is computable
by an arithmetic circuit of size s (respectively, by an arithmetic branching program of size s) …

We develop algorithms for writing a polynomial as sums of powers of low degree
polynomials in the non-degenerate case. This problem generalizes symmetric tensor …

Arithmetic complexity is considered simpler to understand than Boolean complexity, namely
computing Boolean functions via logical gates. And indeed, we seem to have significantly …