tag:blogger.com,1999:blog-3722233.post80531775970903263..comments2024-04-13T02:40:13.964-05:00Comments on Computational Complexity: PH Infinite Under a Random OracleLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-5704629512461562502015-12-28T19:07:58.838-06:002015-12-28T19:07:58.838-06:00I can see why this could let us know that if the p...I can see why this could let us know that if the poly hierarchy does collapse, then we're going to have to be a bit more clever in showing how it does...but I still don't have much intuition on why this gives us evidence that the poly hierarchy is infinite.<br /><br />That is, since the random oracle hypothesis is false, why does this tell us anything about the poly hierarchy being infinite?<br />The fact that IP is separated from PSPACE via a random oracle with probability 1, makes me lose all trust in in oracles saying something is separate.<br />Is there an intuition I'm missing? Or is this just a nice result in piecing together the landscape of the poly hierarchy?Anonymoushttps://www.blogger.com/profile/05260705122889615843noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49403342525882419832015-04-16T11:28:47.750-05:002015-04-16T11:28:47.750-05:00All the random oracle results about complexity cla...All the random oracle results about complexity classes, including this one, hold for all Martin-Löf random oracles. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65627817156280274332015-04-16T11:26:57.678-05:002015-04-16T11:26:57.678-05:00You should think of an input to the circuit corres...You should think of an input to the circuit corresponding to whether a string is in the oracle. Chapter 7 of Håstad's <a href="https://www.nada.kth.se/~johanh/thesis.pdf" rel="nofollow">PhD Thesis</a> works out this connection in full detail. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20246119308736559462015-04-16T09:31:43.538-05:002015-04-16T09:31:43.538-05:00What is known about constructive randomness, such ...What is known about constructive randomness, such as Martin-Löf random oracles? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80837089569606177422015-04-16T09:05:34.149-05:002015-04-16T09:05:34.149-05:00"showed that there were functions that had sm..."showed that there were functions that had small depth d+1 circuits but large depth d circuits which was needed for the oracle."<br /><br />I really don't understand this sentence. What was "needed for the oracle"? How does this result about bounded depth circuits relates to oracles? Anonymousnoreply@blogger.com