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 …

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 study the arithmetic complexity of iterated matrix multiplication. We show that any
multilinear homogeneous depth 4 arithmetic formula computing the product of d generic …

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 develop algorithms for writing a polynomial as sums of powers of low degree
polynomials in the non-degenerate case. This problem generalizes symmetric tensor …

We introduce a new and natural algebraic proof system, whose complexity measure is
essentially the algebraic circuit size of Nullstellensatz certificates. This enables us to exhibit …

Kayal has recently introduced the method of shifted partial derivatives as a way to give the
first exponential lower bound for computing an explicit polynomial as a sum of powers of …

A recent breakthrough work of Limaye, Srinivasan and Tavenas [Nutan Limaye et al., 2021]
proved superpolynomial lower bounds for low-depth arithmetic circuits via a" hardness …

We observe that a certain kind of algebraic proof-which covers essentially all known
algebraic circuit lower bounds to date-cannot be used to prove lower bounds against VP if …

The complexity of Iterated Matrix Multiplication (IMM) is a central theme in Computational
Complexity theory, as the problem is closely related to the problem of separating various …