This work is licensed under a
Creative Commons License.
|
Friday, November 19, 2004
Zig-Zag Connectivity
Posted by Lance
The Zig-Zag Graph Product (Reingold-Vadhan-Wigderson) gave a new way to create expander graphs, graphs on n vertices with constant degree such that for some ε>0 and every subset of the vertices S with |S|≤n/2, |S∪N(S)|≥(1+ε)|S| where N(S) is the set of neighbors of vertices of S.The zig-zag expander construction was not as simple as previous constructions nor did it have as good an expansion property. It did have one thing the other constructions lacked: a simple and beautiful proof of expansion.
The zig-zag construction had another property, a compact representation of the expander from the original graph. Reingold used this property to convert an arbitrary undirected graph to an expander in logarithmic space, the basis of his new result giving a log-space algorithm for undirected connectivity.
Why did George Lucas wait so long between the third and fourth Star Wars movies? He wanted the technology of movie making to catch up to his vision for the movie. Computational Complexity can also tell this story. We hit a wall a decade ago in reducing the space needed to solve graph connectivity. We needed a new technology (zig-zag product) and someone (Reingold) realizing they could use this technology to solve the problem.
8:47 AM #
-
"between the third and fourth Star Wars movies"
Of course, you mean between the sixth and first. ;-)
-
I would never denigrate Reingold's beautiful result by comparing it to Star Wars Episode I.
(Incidentally, he doesn't actually need the zig-zag product; the replacement product works just fine.)
Links to this post:
Weblog Home
Archives
