Parallel algorithms for directed st-connectivity Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. What is the best known parallel algorithm for directed st-connectivity ? Please state the running time, deterministic/randomized algorithm and the PRAM model used (assuming the number of processors is polynomial). Are there any $o({\log}^2{n})$ time parallel algorithms known for any special cases of directed st-connectivity ?
Directed s-t reachability can easily be done using O($n^3$) processors and O$(\log n$) time on a CRCW-PRAM, or in O($n^\omega$) processors and  O($\log^2 n$) time on a EREW-PRAM
 where $\omega&lt;2.376$ is the matrix multiplication exponent and $n$ is the number of vertices. The following paper claims O($n^\omega$) and  O($\log n$) time on a CREW-PRAM: "Optimal Parallel Algorithms
for Transitive Closure and Point Location
in Planar Structures" by Tamassia and Vitter. Other papers claim the same thing and cite the Karp and Ramachandran survey (Parallel algorithms for shared-memory machines, in: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science). The survey itself does mention that transitive closure is in AC1 and hence can be solved in O(log n) time on a CRCW-PRAM, but the part about CREW-PRAM is missing.

All Strassen-like algorithms for matrix multiplication (including the one by Coppersmith-Winograd) are essentially parallel algorithms that run in O$(\log n)$ time; transitive closure incurs an extra log (but if you allow unbounded fan-in the trivial O($n^3$) matrix mult can be done in constant depth and so reachability is in O$(\log n)$ time on a CRCW-PRAM). It's an open problem to improve the number of processors from the current best ~$n^{2.376}$; it is also a major open problem if reachability is in NC1, as it would imply L=NL among other things.