Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #1
Authors: Bin Fu
Accepted on: 22nd November 2013 21:26
Downloads: 781
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
Downloads: 1526
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
Downloads: 841
Keywords: 


Abstract:

Two notions of polynomial identity testing
are defined. Their difference and connection
are compared.




ISSN 1433-8092 | Imprint