In their paper Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds, Kabanets and Impagliazzo prove that if $BPP=P$ then either $(i) NEXP \nsubseteq P_{/poly}$ or $(ii)$ permanent is not computable by poly-size arithmetic circuits .

Yet they claim that derandomizing Polynomial Identity Testing is essentially equivalent to proving arithmetic circuit lower bounds for NEXP. Where did the part about the permanent go ? My question is how come they say it's essentially equivalent.

My guess is that in some (morally speaking) way computing the permanent is in $NEXP$

  • $\begingroup$ Computing permanent is in FP^PP which is in FNEXP. $\endgroup$
    – Mr.
    Sep 24 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.