__
Revision #1 to TR13-157 | 22nd November 2013 21:26
__
#### Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

Revision #1
Authors:

Bin Fu
Accepted on: 22nd November 2013 21:26

Downloads: 1037

Keywords:

**Abstract:**
We show that

derandomizing polynomial identity testing over an arbitrary finite

field implies that NEXP does not have polynomial size boolean

circuits. In other words, for any finite field F(q) of size q,

$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where

$PIT_q$ is the polynomial identity testing problem over F(q), and

NSUBEXP is the nondeterministic subexpoential time class of

languages. Our result is in contract to Kabanets and Impagliazzo's

existing theorem that derandomizing the polynomial identity testing

in the integer ring Z implies that NEXP does have polynomial

size boolean circuits or permanent over Z does not have polynomial

size arithmetic circuits.

__
TR13-157 | 11th November 2013 06:13
__

#### Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

TR13-157
Authors:

Bin Fu
Publication: 15th November 2013 20:24

Downloads: 2255

Keywords:

**Abstract:**
We show that

derandomizing polynomial identity testing over an arbitrary finite

field implies that NEXP does not have polynomial size boolean

circuits. In other words, for any finite field F(q) of size q,

$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where

$PIT_q$ is the polynomial identity testing problem over F(q), and

NSUBEXP is the nondeterministic subexpoential time class of

languages. Our result is in contract to Kabanets and Impagliazzo's

existing theorem that derandomizing the polynomial identity testing

in the integer ring Z implies that NEXP does have polynomial

size boolean circuits or permanent over Z does not have polynomial

size arithmetic circuits.