Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-135 | 9th October 2011 21:44

Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes



We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot NEXP$ does not have $poly$ size constant-free arithmetic circuits.

2. $a\cdot NEXP^{RP}$ does not have $poly$ size constant-free arithmetic circuits.

3. For every fixed $k$, $a\cdot MA$ does not have arithmetic circuits of size $n^k$.

Items 1 and 2 strengthen two results due to Kabanets and Impagliazzo. The third item improves a lower bound due to Santhanam.

We consider the special case low-PIT of identity testing for (constant-free) arithmetic circuits with low formal degree, and give improved hardness-to-randomness trade-offs that apply to this case.

Combining our results for both directions of the hardness-randomness connection, we demonstrate a case where derandomization of PIT and proving lower bounds are equivalent. Namely, we show that low-PIT is infinitely often in $NTIME[2^{n^{o(1)}}]/n^{o(1)}$ if and only if there exists a family of multilinear polynomials in $a\cdot NE/lin$ that requires constant-free arithmetic circuits of super-polynomial size and formal degree.

ISSN 1433-8092 | Imprint