Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-133 | 4th October 2011 16:45

Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent


Authors: Maurice Jansen, Rahul Santhanam
Publication: 5th October 2011 01:16
Downloads: 3331


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
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.

ISSN 1433-8092 | Imprint