Arithmetic circuits with locally low algebraic rank

Mrinal Kumar, Shubhangi Saraf

Research output: Contribution to journalArticle

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 = 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.

Original languageEnglish (US)
JournalTheory of Computing
Volume13
DOIs
StatePublished - Sep 1 2017

Fingerprint

Arithmetic Circuits
Networks (circuits)
Polynomials
Hitting Set
Polynomial
Lower bound
Homogeneity
Transcendence
Polynomial Identities
Monomial
Partial derivative
Natural Extension

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

@article{618087eeb03a457cadac28299bf93d17,
title = "Arithmetic circuits with locally low algebraic rank",
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 = 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.",
keywords = "Algebraic rank, Arithmetic circuits, Hitting sets, Lower bounds, Nonhomogeneous depth-4 circuits, Partial derivatives, Polynomial identity testing, Projected shifted partials",
author = "Mrinal Kumar and Shubhangi Saraf",
year = "2017",
month = "9",
day = "1",
doi = "10.4086/toc.2017.v013a006",
language = "English (US)",
volume = "13",
journal = "Theory of Computing",
issn = "1557-2862",
publisher = "University of Chicago, Department of Computer Science",

}

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

In: Theory of Computing, Vol. 13, 01.09.2017.

Research output: Contribution to journalArticle

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 -