TR11-133 Authors: Maurice Jansen, Rahul Santhanam

Publication: 5th October 2011 01:16

Downloads: 1167

Keywords:

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.