Theory of Computing
-------------------
Title : Arithmetic Circuits with Locally Low Algebraic Rank
Authors : Mrinal Kumar and Shubhangi Saraf
Volume : 13
Number : 6
Pages : 1-33
URL : http://www.theoryofcomputing.org/articles/v013a006
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 $\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.