Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

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
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.

Paper:

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
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.

Comment(s):

Comment #1 to TR13-157 | 24th November 2013 19:34

Comments on Two Definitions of Polynomial Identity Testing Problems

Comment #1
Authors: Bin Fu
Accepted on: 24th November 2013 19:34