tag:blogger.com,1999:blog-3722233.post5076814376972063462..comments2024-03-28T14:56:46.834-05:00Comments on Computational Complexity: The hierarchy and GapPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-289886855692426462021-09-06T13:05:10.503-05:002021-09-06T13:05:10.503-05:00While on the question of derandomizing [VV85], her...While on the question of derandomizing [VV85], here is a fine question: Is there a Pseudo-deterministic RP reduction from SAT to USAT, i.e., the reduction can use random bits but reruns of the reduction should produce the same instance of USAT with very high probability. Vijay Vaziranihttps://www.blogger.com/profile/17192690647930757263noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2856763062884133692021-09-05T09:07:59.714-05:002021-09-05T09:07:59.714-05:00Probably not a full converse but it would be inter...Probably not a full converse but it would be interesting to see if there is some circuit lower bound one could obtain from a deterministic version of Toda-Ogihara. I'll leave that as an open question.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65919710145302286462021-09-04T21:37:38.902-05:002021-09-04T21:37:38.902-05:00Can there be a converse such as deterministic Toda...Can there be a converse such as deterministic Toda-Ogihara implies the time space separation? Or is it possible results such as EXP in PSPACE abd deterministic Toda-Ogihara are both simultaneously possible as far as we know?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79733600406434670252021-09-04T11:00:50.072-05:002021-09-04T11:00:50.072-05:00Great question. The proof of the full Toda-Ogihara...Great question. The proof of the full Toda-Ogihara result requires a version of Valiant-Vazirani relative to the polynomial-time hierarchy and thus a stronger derandomization assumption. An assumption like DTIME(2^n) not in DSPACE(2^{o(n)}) will give you a PRG sufficient to fully derandomize Toda-Ogihara.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17764044026567802112021-09-03T18:06:27.359-05:002021-09-03T18:06:27.359-05:00Does derandomization of Valiant Vazirani derandomi...Does derandomization of Valiant Vazirani derandomize the full result or only this example?Anonymousnoreply@blogger.com