Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RANDOMNESS-HARDNESS TRADEOFFS:
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 ... more >>>