Projects per year
Abstract / Description of output
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 bruteforce 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 constantfree1 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 constantfree 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 widelybelieved assumption that poly size Boolean circuits cannot compute the Permanent of a 0,1matrix over Z. The hypothesis can also be easily derived from the ShubSmale τ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 randomnesstohardness theorem to prove the following unconditional result for Permanent: either Permanent does not have uniform constantdepth threshold circuits of subexponential size, or Permanent does not have polynomialsize constantfree 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 subpolynomial space, or logarithmic space does not have uniform constantdepth threshold circuits of polynomial size.
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 constantfree1 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 constantfree 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 widelybelieved assumption that poly size Boolean circuits cannot compute the Permanent of a 0,1matrix over Z. The hypothesis can also be easily derived from the ShubSmale τ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 randomnesstohardness theorem to prove the following unconditional result for Permanent: either Permanent does not have uniform constantdepth threshold circuits of subexponential size, or Permanent does not have polynomialsize constantfree 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 subpolynomial space, or logarithmic space does not have uniform constantdepth threshold circuits of polynomial size.
Original language  English 

Title of host publication  Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 810, 2012 
Publisher  ACM 
Pages  496506 
Number of pages  11 
ISBN (Electronic)  9781450311151 
DOIs  
Publication status  Published  2012 
Fingerprint
Dive into the research topics of 'Marginal hitting sets imply superpolynomial lower bounds for permanent'. Together they form a unique fingerprint.Projects
 1 Finished

Hierarchies, Circuit Lower Bounds and Pseudorandomness
Santhanam, R.
1/10/10 → 31/12/12
Project: Research