4
$\begingroup$

(This is a bit of follow-up to https://cstheory.stackexchange.com/posts/comments/93266 but is a distinct enough question I though it should be on its own.)

In Omer Reingold's logspace USTCON algorithm, he uses zig-zag products; the zig-zag product is attractive in that if $H$ is a good expander, then $G{\,\,\,\mathbin{{ \hspace{-.4em}\bigcirc\hspace{-.75em}{\rm z}\hspace{.15em}}}\,} H$ is "not much worse" of an expander then $G$. Then $G$ can be powered, to make it a much better expander; and balancing these two operations allows him to turn $G$ into a larger, good expander.

The replacement product is a few senses, simpler to understand: steps on it naturally correspond to a step in either $G$ or $H$. In "Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders", Reingold at all actually mention that replacement products aren't much worse than zig-zag products: the cube of the replacement product contains all of the edges of the zig-zag product, so has at least as good connectivity.

This means that the proof for $L=SL$ should be able to accomplished with only the replacement product, instead of the zig-zag product. In terms of the loosest bound: instead of taking the 8th power of the graph, the 24th power is taken; and then the replacement product is used instead. This means taking a $(D^{48}, D, 1/2)$ graph to start with instead of $(D^{16}, D, 1/2)$, but these also exist by the same construction they used (just plugging in different numbers).

Assuming that I'm not somehow totally misled in the above -- why is the result so often stated with zig-zag products? Replacement products seem more natural, and clearly fulfill the same requirements. Currently the only proof of their expansion properties I could find was in terms of zig-zag products, but I don't expect it to be too difficult to deal with them directly. Maybe my question really should be -- why are zig-zag products preferred over replacement products?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Here is a paper using replacement products instead of zig-zag: eccc.weizmann.ac.il/report/2016/144 $\endgroup$
    – Emil Jeřábek
    Apr 27, 2018 at 11:20
  • 1
    $\begingroup$ Emil, I think you should make that an answer. $\endgroup$
    – Jan Johannsen
    Apr 27, 2018 at 11:51
  • 1
    $\begingroup$ @JanJohannsen Well, it doesn’t seem to me that I answered the main question: “why is the result so often stated with zig-zag products”. My comment just confirms the premise that the result can, indeed, be shown using replacement product. (Sort of. The paper presents it as an expander construction rather than a proof of L = SL.) $\endgroup$
    – Emil Jeřábek
    Apr 27, 2018 at 18:22
  • $\begingroup$ Either way it's an interesting paper, thanks Emil! They give slightly better bounds ($e_G^2 e_H/48$ vs. $e_G^2 e_H/80$) than what I had seen before. I realized that the thing I described in my post above doesn't immediately work as the replacement product is $D+1$ regular, not $D$. You would need to pad with a lot of edges and make constants worse. $\endgroup$
    – Alex Meiburg
    Apr 27, 2018 at 23:27
  • $\begingroup$ The proof of Reingold's theorem in Arora & Barak's book uses the replacement product. $\endgroup$
    – didest
    Apr 28, 2018 at 16:16

1 Answer 1

Reset to default
4
$\begingroup$

There is a paper already in 2005 that describes how to do this... See https://people.seas.harvard.edu/~salil/research/derand_squaring-abs.html

I cannot say why people use zig-zag instead, other than perhaps they found the original reference readable enough that they did not need to look at secondary literature. At least for teaching purposes it seems the replacement product is simpler, as the above link shows.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.