Volume 13 (2017) Article 6 pp. 1-33
CCC 2016 Special Issue

Arithmetic Circuits with Locally Low Algebraic Rank

by Mrinal Kumar and Shubhangi Saraf

Received: April 30, 2016
Revised: June 7, 2017
Published: September 1, 2017

$ \newcommand{\spnew}{\Sigma{\Pi^{(k)}}\Sigma\Pi} \newcommand{\spnewn}{\Sigma{\Pi^{(n)}}\Sigma\Pi} \newcommand{\spnewbounded}{\Sigma{\Pi^{(k)}}\Sigma\Pi^{[d]}} \newcommand{\VNP}{\mathtt{VNP}} \def\poly{\textsf{poly}} $

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 $\neq$ 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 \[ P = \sum_{i = 1}^T Q_{i1}\cdot Q_{i2}\cdot \cdots Q_{it} \; , \] where the $Q_{ij}$ are given by their monomial expansion. Homogeneity adds the constraint that for every $i \in [T]$, $\sum_{j} \deg(Q_{ij}) = n$. We study an extension, where, for every $i \in [T]$, the algebraic rank of the set $\{Q_{i1}, Q_{i2}, \ldots ,Q_{it}\}$ of polynomials is at most some parameter $k$. We call this the class of $\spnew$ circuits. Already for $k = n$, these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular $t \leq n$ (and hence $k \leq 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 $\{P_n\}$ of degree $n$ in $N = n^{O(1)}$ variables in $\VNP$, such that any $\spnewn$ circuit computing $P_n$ has size at least $\exp{(\Omega(\sqrt{n}\log N))}$. 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 $\spnew$ circuits in the restricted setting where $T\cdot k \leq n$.

2. Hitting sets. Let $\spnewbounded$ be the class of $\spnew$ circuits with bottom fan-in at most $d$. We show that if $d$ and $k$ are at most $\poly(\log N)$, then there is an explicit hitting set for $\spnewbounded$ 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(\log N)$.

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.

A conference version of this paper appeared in the Proceedings of the 31st Conference on Computational Complexity, 2016..

DOI: 10.4086/toc.2017.v013a006

© 2017 Mrinal Kumar and Shubhangi Saraf
Licensed under a Creative Commons Attribution License (CC-BY)