This work is licensed under a
Creative Commons License.
|
Tuesday, June 29, 2004
FOCS Accepted Papers
Posted by Lance
The list of accepted papers for the upcoming FOCS conference in Rome is out. [Thanks Suresh]A few complexity papers to note: Ran Raz finds easy languages with no log-depth multilinear circuits. Andris Ambainis and Mario Szegedy have separate papers showing nice applications of quantum "random" walks. Barak, Impagliazzo and Wigderson show how to do extract nearly uniform distributions from multiple independent random sources as opposed to one random source and a few truly random bits. And lots more.
5:13 PM #
-
Ok, I'll bite :-) "Lots more" includes a paper of
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 previous paper of Boaz Barak's, comes close: if we consider algorithms that use one bit of input-length-dependent "advice", then the answer is yes.
--Siva
Links to this post:
Weblog Home
Archives
