Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, it suffices to query $f$ on an arbitrary test set of $r+1$ points. Could this brute-force method be improved upon by {\em a single point}? We develop a framework where such a marginal improvement implies that Permanent does not have polynomial size arithmetic circuits.
More formally, we formulate the following hypothesis for any field of characteristic zero: There is a fixed depth $d$
and some function $s(n) = O(n)$, such that for arbitrarily small $\epsilon > 0$, there exists a hitting set $\mathcal{H}_n\subset \Integers$ of size at most $2^{s(n^\epsilon)}$ against univariate polynomials of degree at most $2^{s(n^\epsilon)}$ computable by size $n$ constant-free arithmetic circuits, where $\mathcal{H}_n$ can be encoded by uniform $\TC^0$ circuits of size $2^{O(n^\epsilon)}$ and depth $d$. We prove that the hypothesis implies that Permanent does not have polynomial size constant-free arithmetic circuits.
Our hypothesis provides a unifying perspective on several important complexity theoretic conjectures, as it
follows from these conjectures for different degree ranges as determined by the function $s(n)$.
We will show that it follows for $s(n) = n$ from the widely-believed assumption that $poly$ size Boolean circuits cannot compute the Permanent of a $0,1$-matrix over $\Integers$. The hypothesis can also be easily derived from the Shub-Smale $\tau$-conjecture, for any $s(n)$ with $s(n)= \omega(\log n)$
and $s(n) = O(n)$. This implies our result strengthens a theorem by B\"{u}rgisser, who derives the same lower bound from the $\tau$-conjecture.
For $s(n) = 0$, the hypothesis follows from the statement that $(n!)$ is
ultimately hard, a statement that is known to imply $\P \neq \NP$ over $\Cee$.
We apply our randomness-to-hardness theorem to prove the following unconditional result for Permanent: either Permanent does not have uniform
constant-depth threshold circuits of sub-exponential size, or Permanent does
not have
polynomial-size constant-free arithmetic circuits.
Turning to the Boolean world, we give a simplified proof of the following
strengthening
of Allender's lower bound \cite{All99} for the (0,1)-Permanent: either the (0,1)-Permanent
is not simultaneously in polynomial time and sub-polynomial space, or logarithmic space does not have uniform constant-depth threshold circuits of polynomial size.
