ECCC-Report TR13-157https://eccc.weizmann.ac.il/report/2013/157Comments and Revisions published for TR13-157en-usSun, 24 Nov 2013 19:34:34 +0200
Comment 1
| Comments on Two Definitions of Polynomial Identity Testing Problems |
Bin Fu
https://eccc.weizmann.ac.il/report/2013/157#comment1Two notions of polynomial identity testing
are defined. Their difference and connection
are compared.Sun, 24 Nov 2013 19:34:34 +0200https://eccc.weizmann.ac.il/report/2013/157#comment1
Revision 1
| Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP |
Bin Fu
https://eccc.weizmann.ac.il/report/2013/157#revision1We 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.
Fri, 22 Nov 2013 21:26:42 +0200https://eccc.weizmann.ac.il/report/2013/157#revision1
Paper TR13-157
| Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP |
Bin Fu
https://eccc.weizmann.ac.il/report/2013/157We 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.
Fri, 15 Nov 2013 20:24:36 +0200https://eccc.weizmann.ac.il/report/2013/157