Arithmetic circuits with locally low algebraic rank

In recent years, there has been a flurry of activity towards proving lower bounds for homogeneous depth-4 arithmetic circuits (Gupta et al., Fournier et al., Kayal et al., Kumar- Saraf), which has brought us very close to statements that are known to imply VP 6= VNP. It is open if these techniques can go beyond homogeneity, and in this paper we make progress in this direction by considering depth-4 circuits of 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(Formula presented.) where the Qij are given by their monomial expansion. Homogeneity adds the constraint that for every i ∈ [T], Σj deg(Qij) = n. We study an extension, where, for every i ∈ [T], the algebraic rank of the set fQi1;Qi2;Qitg of polynomials is at most some parameter k. We call this the class of Σ∏^(k)Σ∏ circuits. Already for k = n, these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular t ≤ n (and hence k ≤ 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 fPng of degree n in N = n^O(1) variables in VNP, such that any Σ∏⁽ⁿ⁾Σ∏ circuit computing Pn has size at least exp(Ω(√nlogN)). This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for homogeneous depth-4 circuits (Kayal et al. and Kumar-Saraf) as well as the Jacobian based lower bounds of Agrawal et al. which worked for Σ∏^(k)Σ∏ circuits in the restricted setting where T ·k n. 2. Hitting sets. Let Σ∏^(k)Σ∏^[d] be the class of Σ∏^(k)Σ∏ circuits with bottom fan-in at most d. We show that if d and k are at most Poly(logN), then there is an explicit hitting set for Σ∏^(k)Σ∏^[d] circuits of size quasipolynomially bounded in N and the size of the circuit. This strengthens a result of Forbes who constructed such quasipolynomial-size hitting sets in the setting where d and t are at most Poly(logN). A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), up to a translation, every polynomial in a set of polynomials can be written as a function of the polynomials in a transcendence basis of the set. We believe this may be of independent interest. We combine this with methods based on shifted partial derivatives to obtain our final results.