AN O(log n log log n) SPACE ALGORITHM FOR UNDIRECTED ST-CONNECTIVITY.

We present a deterministic O(log n log log n) space algorithm for undirected st-connectivity. It is based on a space-efficient simulation of the deterministic EREW algorithm of Chong and Lam [J. Algorithms, 18 (1995), pp. 378-402], an approach suggested by Prof. Vijaya Ramachandran, and uses the universal exploration sequences for trees constructed by Koucký in [Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 21-27]. Our result improves the O(log^4/3 n) bound of Armoni et al. in [Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1997, pp. 230-239] and is a big step towards the optimal O(log n). Independently of our result and using a different set of techniques, the optimal bound was achieved by Reingold in [Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 376-385]. [ABSTRACT FROM AUTHOR]