## Abstract

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 Σ∏^{(n)}Σ∏ 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1-33 |

Number of pages | 33 |

Journal | Theory of Computing |

Volume | 13 |

DOIs | |

State | Published - Sep 1 2017 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computational Theory and Mathematics

## Keywords

- Algebraic rank
- Arithmetic circuits
- Hitting sets
- Lower bounds
- Nonhomogeneous depth-4 circuits
- Partial derivatives
- Polynomial identity testing
- Projected shifted partials