Arithmetic circuits with locally low algebraic rank

Mrinal Kumar, Shubhangi Saraf

Research output: Contribution to journalArticle

2 Scopus citations

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

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

Fingerprint Dive into the research topics of 'Arithmetic circuits with locally low algebraic rank'. Together they form a unique fingerprint.

  • Cite this