tag:blogger.com,1999:blog-3722233.post108854724262048024..comments2024-10-07T03:56:38.595-05:00Comments on Computational Complexity: FOCS Accepted PapersLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-1088560385150093862004-06-29T20:53:00.000-05:002004-06-29T20:53:00.000-05:00Ok, I'll bite :-) "Lots more" includes a paper of...Ok, I'll bite :-) "Lots more" includes a paper of<br />Fortnow and Santhanam that addresses a basic question concerning randomized computation (of the kind one cares the most about) -- does more time give us power to solve more problems? Unlike deterministic computation, for which a resounding "yes" answer was shown in the mid-1960's, this question is still open. The Fortnow--Santhanam paper, improving a <A HREF="http://www.blogger.com/r?http%3A%2F%2Fwww.math.ias.edu%2F%7Eboaz%2FPapers%2Fbptime.html"> previous paper </A> of <A HREF="http://www.blogger.com/r?http%3A%2F%2Fwww.math.ias.edu%2F%7Eboaz"> Boaz Barak</A>'s, comes close: if we consider algorithms that use one bit of input-length-dependent "advice", then the answer is yes.<br /><br />--SivaAnonymousnoreply@blogger.com