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 dand some function s(n)=O(n), such that for arbitrarily small 0">0, there exists a hitting set n\Integers of size at most 2s(n) against univariate polynomials of degree at most 2s(n) computable by size n constant-free arithmetic circuits, where n can be encoded by uniform \TC0 circuits of size 2O(n) 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 01 -matrix over \Integers. The hypothesis can also be easily derived from the Shub-Smale -conjecture, for any s(n) with s(n)=(logn)and s(n)=O(n). This implies our result strengthens a theorem by B\"{u}rgisser, who derives the same lower bound from the -conjecture. For s(n)=0, the hypothesis follows from the statement that (n!) is ultimately hard, a statement that is known to imply \P=\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 strengtheningof Allender's lower bound \cite{All99} for the (0,1)-Permanent: either the (0,1)-Permanentis not simultaneously in polynomial time and sub-polynomial space, or logarithmic space does not have uniform constant-depth threshold circuits of polynomial size.