Revised: June 7, 2017
Published: September 1, 2017
Abstract: [Plain Text Version]
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.
- 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$.
- 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..