In layman's terms, suppose you have a big maze, far too big to fit into your computer's memory. You can only ask questions of the form: given two locations A and B, are A and B directly connected? Reingold's result shows that you can determine whether there is a path from the entrance to the exit using only an amount of memory equivalent to storing a constant number of maze locations.
Wednesday, November 10, 2004
Undirected Connectivity in Log Space
Omer Reingold has shown
Undirected
s-t Connectivity in Deterministic Log-Space. This settles a
long-standing open question for a problem previously known to be in
randomized logarithmic space
(Aleliunas-Karp-Lipton-Lovász-Rackoff) and deterministic
log4/3 space (Armoni-TaShma-Wigderson-Zhou). Wow!
Subscribe to:
Post Comments (Atom)
This is obviously a tremendous result, but it must be remembered that there already existed a log^(4/3)-space result and this is not acknowledged "in layman terms".
ReplyDeleteThis is a great result. Sometimes it feels like we never get anywhere on the major problems, but every year or two something like this comes down the pike. It's encouraging, and for me, it came at just the right time.
ReplyDeleteLately, my thoughts during my morning walk to the office had been clouded with disappointment over the US election results. But Omer's paper got me back in the groove, and today I was thinking about expander graphs when I should have been concentrating on traffic!
"... remember only a constant number of maze locations..."
ReplyDeleteNot sure, really. Reingold's algorithm also seems to require log N many registers capable of holding a constant size info. Similar, but not quite. (N = size of maze).
This is a great result. Can't wait to read it...
ReplyDeleteNot necessary to wait. See here or there.
ReplyDelete