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       : https://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.