The paper presents a simple construction of polynomial length universal traversal sequences for cycles. These universal traversal sequences are log-space (even $NC^1$) constructible and are of length $O(n^{4.03})$. Our result improves the previously known upper-bound $O(n^{4.76})$ for log-space constructible universal traversal sequences for cycles. more >>>

For every $\epsilon>0$, we present a {\em deterministic}\/ log-space algorithm that correctly decides undirected graph connectivity on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs. The same holds for every problem in Symmetric Log-space (i.e., $\SL$). Making no assumptions (and in particular not assuming the ERH), we present a ... more >>>

We highlight a common theme in four relatively recent works that establish remarkable results by an iterative approach. Starting from a trivial construct, each of these works applies an ingeniously designed sequence of iterations that yields the desired result, which is highly non-trivial. Furthermore, in each iteration, the construct is ... more >>>