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.
Ok, I'll bite :-) "Lots more" includes a paper of
ReplyDeleteFortnow 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