Thursday, February 06, 2014

Favorite Theorems: Connecting in Log Space

We start the favorite theorems with a result that might surprise many is still less than ten years old.

Intuitively, this result says you can tell if two points are connected in a complex maze by only having to remember the equivalent of a constant number of locations in the maze. Reingold's algorithm builds an expander graph based on the zig-zag construction in a very clever way that uses very little space to construct and to check that two points connect.

In 1979, Aleliunas, Karp, Lipton, Lovász and Rackoff showed that one can solve s-t connectivity in randomized logarithmic space by taking a random walk on the graph. My last favorite theorem from 2004 talked about derandomizing space algorithms and before Reingold the best algorithm for s-t connectivity required log4/3 space. Indepently of Reingold, Vladimir Trifonov gave a O(log n log log n) space algorithm for s-t connectivity, a victim of bad timing.

One neat implication of Reingold's result is a new and simpler characterization of log-space as the set of problems expressible in first-order logic with ordering and symmetric transitive closure.

After Reingold's result we might have expected solutions to a number of related problems but we didn't see much progress.
• Can every randomized log-space algorithm be derandomized in log space?
• Do there exist log-space computable universal traversal sequences?
• Can we solve directed s-t connectivity better than Savitch
• Can we modify Reingold's algorithm to bring log space into NC1?

6 comments:

1. At the time it was proven was it surprising that it was TRUE or surprising that it was PROVABLE or was it not that surprising (STILL a great result of course).

1. The statement of the theorem itself wasn't surprising since we generally believe that good derandomization is possible and it was already known that connectivity is in randomized log space. It's not surprising that the result is provable, but it was surprising that Reingold could prove it using current technology.

2. I DETECT based on subtle CLUES that "CAAR REU" might be GASARCH in DISGUISE.

3. But has anybody succeed to prove that CONN requires about n^3 gates in a monotone circuit with fanin-2 AND and OR gates? By Floyd-Warshall dynamic programming algorithm, so many gates are enough.

And what about STCONN? Do we need also here about n^3 gates?

Space is ok. But why nobody is interested in *time*?

4. > Intuitively, this result says you can tell if two points are connected in a complex maze by only having to remember the equivalent of a constant number of locations in the maze.

Does it work if we are not allowed to do arithmetic on the index of the locations? Does it work with literally a constant number of locations instead of 'the equivalent of a constant number of locations'?

5. @Anonymous 4:15, there is a paper by Martin Hofmann and Ulrich Schoepp in LICS 2009 giving a negative answer in a certain way:
http://www2.tcs.ifi.lmu.de/~schoepp/Docs/reach_conf.pdf