# Can $L=SL$ be shown with the replacement product instead of the zig-zag product?

(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?

• Here is a paper using replacement products instead of zig-zag: eccc.weizmann.ac.il/report/2016/144 Apr 27, 2018 at 11:20
• Emil, I think you should make that an answer. Apr 27, 2018 at 11:51
• @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.) Apr 27, 2018 at 18:22
• 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. Apr 27, 2018 at 23:27
• The proof of Reingold's theorem in Arora & Barak's book uses the replacement product. Apr 28, 2018 at 16:16