In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree $n$ in $n^2$ variables such that any homogeneous depth 4 arithmetic circuit computing it must have size $n^{\Omega(\log \log n)}$.

Our results extend ... more >>>

This text is a development of a preprint of Ankit Gupta.

We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$ circuits with bounded top fanin.
This approach is similar to Kayal-Saraf approach for depth-$3$ circuits. Kayal and Saraf based their ... more >>>

We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form
\[
\Sigma^{[r]}\!\wedge^{[d]}\!\Sigma^{[s]}\!\Pi^{[\delta]}.
\]
This model generalizes Waring decompositions and diagonal circuits, and captures sums of powers of low-degree sparse polynomials. Specifically, each circuit computes a sum of $r$ terms, where each term is ... more >>>

We study depth-$5$ algebraic circuits over small finite fields with restricted fan-in of the top product gates. We show that there exists an explicit degree-$d$ polynomial $P(\mathbf{x})$ such that any $\Sigma \Pi^{[\mathrm{poly(d)}]} \Sigma \Pi \Sigma$ circuit, computing $P(\mathbf{x})$, over a small finite field, requires size $2^{\Omega(\sqrt{d})}$. Our work builds upon ... more >>>