  We study the complexity of representing polynomials as a sum of products of
polynomials in few variables. More precisely, we study representations of the
form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$ such that each $Q_{ij}$ is
an arbitrary polynomial that depends on at most $s$ variables. We prove the
following results.
  1. Over fields of characteristic zero, for every constant $\mu$ such that $0
\leq \mu < 1$, we give an explicit family of polynomials $\{P_{N}\}$, where
$P_{N}$ is of degree $n$ in $N = n^{O(1)}$ variables, such that any
representation of the above type for $P_{N}$ with $s = N^{\mu}$ requires $Td
\geq n^{\Omega(\sqrt{n})}$. This strengthens a recent result of Kayal and Saha
[KS14a] which showed similar lower bounds for the model of sums of products of
linear forms in few variables. It is known that any asymptotic improvement in
the exponent of the lower bounds (even for $s = \sqrt{n}$) would separate VP
and VNP[KS14a].
  2. We obtain a deterministic subexponential time blackbox polynomial identity
testing (PIT) algorithm for circuits computed by the above model when $T$ and
the individual degree of each variable in $P$ are at most $\log^{O(1)} N$ and
$s \leq N^{\mu}$ for any constant $\mu < 1/2$. We get quasipolynomial running
time when $s < \log^{O(1)} N$. The PIT algorithm is obtained by combining our
lower bounds with the hardness-randomness tradeoffs developed in [DSY09, KI04].
To the best of our knowledge, this is the first nontrivial PIT algorithm for
this model (even for the case $s=2$), and the first nontrivial PIT algorithm
obtained from lower bounds for small depth circuits.
