We show that RL is contained in L/O(n), i.e., any language computable
in randomized logarithmic space can be computed in deterministic
logarithmic space with a linear amount of non-uniform advice. To
prove our result we show how to take an ultra-low space walk on
the Gabber-Galil expander graph.

more >>>

The Local Search problem, which finds a
local minimum of a black-box function on a given graph, is of both
practical and theoretical importance to many areas in computer
science and natural sciences. In this paper, we show that for the
Boolean hypercube $\B^n$, the randomized query complexity of Local
more >>>

Theoretical computer scientists have been debating the role of
oracles since the 1970's. This paper illustrates both that oracles
can give us nontrivial insights about the barrier problems in
circuit complexity, and that they need not prevent us from trying to
solve those problems.

First, we ... more >>>