Marginal hitting sets imply super-polynomial lower bounds for permanent

Maurice J. Jansen, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 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 ε > 0, there exists a hitting set Hn ⊂ Z of size at most 2s(nε) against univariate polynomials of degree at most 2s(nε) computable by size n constant-free1 arithmetic circuits, where Hn 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 0,1-matrix over Z. The hypothesis can also be easily derived from the Shub-Smale τ-conjecture [21], for any s(n) with s(n) = ω(log n) and s(n) = O(n). This implies our result strengthens a theorem by Bürgisser [4], 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 C [21].

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 [2] 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.
Original languageEnglish
Title of host publicationInnovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012
PublisherACM
Pages496-506
Number of pages11
ISBN (Electronic)978-1-4503-1115-1
DOIs
Publication statusPublished - 2012

Fingerprint

Dive into the research topics of 'Marginal hitting sets imply super-polynomial lower bounds for permanent'. Together they form a unique fingerprint.

Cite this