Hi all,

As most of you may already know, it was proved by Reingold that
undirected st-connectivity is in log space. The proof uses the zig-zag
product of graphs. See, e.g.,
http://www.weizmann.ac.il/mathusers/reingold/publications/sl.ps

I've seen elsewhere that the logarithmic-space bound is optimal, where
it is stated as a trivial fact. Somehow I can't figure out why. Is it
because we need logarithmic space just to store a single pointer?

Does anyone want to comment on that? :)

Best,
Ching-Lueh