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!

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.

Posted by at 4:04 PM

5 comments:

  1. 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".
    ReplyDelete
  2. This 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.

    Lately, 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!
    ReplyDelete
  3. "... remember only a constant number of maze locations..."

    Not 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).
    ReplyDelete
  4. This is a great result. Can't wait to read it...
    ReplyDelete
  5. Not necessary to wait. See here or there.
    ReplyDelete

Subscribe to: Post Comments (Atom)