Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would yield such results for general circuits (that is, the complexity class VP).
We show that if we can design poly($s$)-time hitting-sets for $\Sigma\wedge^a\Sigma\Pi^{O(\log s)}$ circuits of size $s$, where $a=\omega(1)$ is arbitrarily small and the number of variables, or arity $n$, is $O(\log s)$, then we can derandomize blackbox PIT for general circuits in quasipolynomial time. Further, this establishes that either E$\not\subseteq$\#P/poly or that VP$\ne$VNP. We call the former model \emph{tiny} diagonal depth-$4$. Note that these are merely polynomials with arity $O(\log s)$ and degree $\omega(\log s)$.
In fact, we show that one only needs a poly($s$)-time hitting-set against individual-degree $a'=\omega(1)$ polynomials that are computable by a size-$s$ arity-$(\log s)$ $\Sigma\Pi\Sigma$ circuit (note: $\Pi$ fanin may be $s$).
Alternatively, we claim that, to understand VP one only needs to find hitting-sets, for depth-$3$, that have a small parameterized complexity.
Another tiny family of interest is when we restrict the arity $n=\omega(1)$ to be arbitrarily small. In parameterized complexity terms: We show that if we can design poly($s,\mu(n)$)-time hitting-sets for size-$s$ arity-$n$ $\Sigma\Pi\Sigma\wedge$ circuits (resp.~$\Sigma\wedge^a\Sigma\Pi$), where function $\mu$ is arbitrary, then we can solve PIT for VP in quasipoly-time, and prove the corresponding lower bounds.
Our methods are strong enough to prove a surprising {\em arity reduction} for PIT-- to solve the general problem completely it suffices to find a blackbox PIT with time-complexity $sd2^{O(n)}$. This suggests that, in algebraic-geometry terms, PIT is inherently an `extremely low'-dimensional (or `extremely low' individual-degree) problem.
One expects that with this severe restriction on $n, a$ and the semantic individual-degree, it should be at least ``exponentially'' easier to design hitting-sets. Indeed, we give several examples of ($\log s$)-variate circuits where a new measure (called {\em cone-size}) helps in devising poly-time hitting-sets, but the same question for their $s$-variate versions is open till date: For eg., diagonal depth-$3$ circuits, and in general, models that have a {\em small} partial derivative space. The latter models are very well studied, following (Nisan \& Wigderson, FOCS'95 \cite{NW95}), but no $sd2^{O(n)}$-time PIT algorithm was known for them.
We also introduce a new concept, called {\em cone-closed basis} isolation, and provide example models where it occurs, or can be achieved by a small shift. This refines the previously studied notions of low-support (resp.~low-cone) rank concentration and least basis isolation in certain ABP models. Cone-closure holds special relevance in the low-arity regime.
