In recent years there has been a flurry of activity proving lower bounds for
homogeneous depth-4 arithmetic circuits [GKKS13, FLMS14, KLSS14, KS14c], which has brought us very close to statements that are known to imply VP $\neq$ VNP. It is a big question to go beyond homogeneity, and in this paper we make progress towards this by considering depth-4 circuits of {\it low algebraic rank}, which are a natural extension of homogeneous depth-4 arithmetic circuits.

A depth-4 circuit is a representation of an $N$-variate, degree $n$ polynomial $P$ as
\[
P = \sum_{i = 1}^T Q_{i1}\cdot Q_{i2}\cdot \cdots Q_{it}
\]

where the $Q_{ij}$ are given by their monomial expansion. Homogeneity adds the constraint that for every $i \in [T]$, $\sum_{j} \text{degree}(Q_{ij}) = n$. We study an extension where, for every $i \in [T]$, the {\it algebraic rank} of the set of polynomials $\{Q_{i1}, Q_{i2}, \ldots ,Q_{it}\}$ is at most some parameter $k$. We call this the class of $\Sigma{\Pi^{(k)}}\Sigma\Pi$ circuits. Already for $k = n$, these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular $t \leq n$ (and hence $k \leq n$).

We study lower bounds and polynomial identity tests for such circuits and prove the following results.

1. Lower bounds : We give an explicit family of polynomials $\{P_n\}$ of degree $n$ in $N = n^{O(1)}$ variables in $VNP$, such that any $\Sigma{\Pi^{(n)}}\Sigma\Pi$ circuit computing $P_n$ has size at least $\exp{(\Omega(\sqrt{n}\log N))}$.
This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for {\it homogeneous} depth-4 circuits[KLSS14, KS14c] as well as the Jacobian based lower bounds of Agrawal et al [ASSS12] which worked for $\Sigma{\Pi^{(k)}}\Sigma\Pi$ circuits in the restricted setting where $T\cdot k \leq n$.

2. Hitting sets : Let $\Sigma{\Pi^{(k)}}\Sigma\Pi^{[d]}$ be the class of $\Sigma{\Pi^{(k)}}\Sigma\Pi$ circuits with bottom fan-in at most $d$. We show that if $d$ and $k$ are at most $\text{poly}(\log N)$, then there is an explicit hitting set for $\Sigma{\Pi^{(k)}}\Sigma\Pi^{[d]}$ circuits of size quasipolynomial in $N$ and the size of the circuit. This strengthens a result of Forbes [For15] which showed such quasipolynomial sized hitting sets in the setting where $d$ and $t$ are at most $\text{poly}(\log N)$.
\end{enumerate}

A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), upto a translation, every polynomial in a set of algebraically dependent polynomials can be written as a function of the polynomials in the transcendence basis. We believe this may be of independent interest. We combine this with shifted partial derivative based methods to obtain our final results.

Minor changes in the latex text in the abstract.

In recent years there has been a flurry of activity proving lower bounds for
homogeneous depth-4 arithmetic circuits [GKKS13, FLMS14, KLSS14, KS14c], which has brought us very close to statements that are known to imply VP $\neq$ VNP. It is a big question to go beyond homogeneity, and in this paper we make progress towards this by considering depth-4 circuits of {\it low algebraic rank}, which are a natural extension of homogeneous depth-4 arithmetic circuits.

A depth-4 circuit is a representation of an $N$-variate, degree $n$ polynomial $P$ as
\[
P = \sum_{i = 1}^T Q_{i1}\cdot Q_{i2}\cdot \cdots Q_{it}
\]

where the $Q_{ij}$ are given by their monomial expansion. Homogeneity adds the constraint that for every $i \in [T]$, $\sum_{j} \text{degree}(Q_{ij}) = n$. We study an extension where, for every $i \in [T]$, the {\it algebraic rank} of the set of polynomials $\{Q_{i1}, Q_{i2}, \ldots ,Q_{it}\}$ is at most some parameter $k$. We call this the class of $\Sigma{\Pi^{(k)}}\Sigma\Pi$ circuits. Already for $k = n$, these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular $t \leq n$ (and hence $k \leq n$).

We study lower bounds and polynomial identity tests for such circuits and prove the following results.

\begin{enumerate}
\item {\bf Lower bounds : } We give an explicit family of polynomials $\{P_n\}$ of degree $n$ in $N = n^{O(1)}$ variables in $VNP$, such that any $\Sigma{\Pi^{(n)}}\Sigma\Pi$ circuit computing $P_n$ has size at least $\exp{(\Omega(\sqrt{n}\log N))}$.
This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for {\it homogeneous} depth-4 circuits[KLSS14, KS14c] as well as the Jacobian based lower bounds of Agrawal et al [ASSS12] which worked for $\Sigma{\Pi^{(k)}}\Sigma\Pi$ circuits in the restricted setting where $T\cdot k \leq n$.

\item {\bf Hitting sets : } Let $\Sigma{\Pi^{(k)}}\Sigma\Pi^{[d]}$ be the class of $\Sigma{\Pi^{(k)}}\Sigma\Pi$ circuits with bottom fan-in at most $d$. We show that if $d$ and $k$ are at most $\text{poly}(\log N)$, then there is an explicit hitting set for $\Sigma{\Pi^{(k)}}\Sigma\Pi^{[d]}$ circuits of size quasipolynomial in $N$ and the size of the circuit. This strengthens a result of Forbes [For15] which showed such quasipolynomial sized hitting sets in the setting where $d$ and $t$ are at most $\text{poly}(\log N)$.
\end{enumerate}

A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), upto a translation, every polynomial in a set of algebraically dependent polynomials can be written as a function of the polynomials in the transcendence basis. We believe this may be of independent interest. We combine this with shifted partial derivative based methods to obtain our final results.