### 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) |
---|---|

Journal | Theory of Computing |

Volume | 13 |

DOIs | |

State | Published - Sep 1 2017 |

### Fingerprint

### 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

### Cite this

}

*Theory of Computing*, vol. 13. https://doi.org/10.4086/toc.2017.v013a006

**Arithmetic circuits with locally low algebraic rank.** / Kumar, Mrinal; Saraf, Shubhangi.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Arithmetic circuits with locally low algebraic rank

AU - Kumar, Mrinal

AU - Saraf, Shubhangi

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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 = nO(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.

AB - 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 = nO(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.

KW - Algebraic rank

KW - Arithmetic circuits

KW - Hitting sets

KW - Lower bounds

KW - Nonhomogeneous depth-4 circuits

KW - Partial derivatives

KW - Polynomial identity testing

KW - Projected shifted partials

UR - http://www.scopus.com/inward/record.url?scp=85044768128&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044768128&partnerID=8YFLogxK

U2 - 10.4086/toc.2017.v013a006

DO - 10.4086/toc.2017.v013a006

M3 - Article

AN - SCOPUS:85044768128

VL - 13

JO - Theory of Computing

JF - Theory of Computing

SN - 1557-2862

ER -