Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>

We consider the minimal number of AND and OR gates in monotone
circuits for quadratic boolean functions, i.e. disjunctions of
length-$2$ monomials. The single level conjecture claims that
monotone single level circuits, i.e. circuits which have only one
level of AND gates, for quadratic functions ... more >>>

In this paper we construct a cyclically invariant Boolean function
whose sensitivity is $\Theta(n^{1/3})$. This result answers two
previously published questions. Tur\'an (1984) asked if any
Boolean function, invariant under some transitive group of
permutations, has sensitivity $\Omega(\sqrt{n})$. Kenyon and Kutin
(2004) asked whether for a ``nice'' function the product ... more >>>