<p>There is a paper already in 2005 that describes how to do this...
See <a href="https://people.seas.harvard.edu/~salil/research/derand_squaring-abs.html" rel="nofollow noreferrer">https://people.seas.harvard.edu/~salil/research/derand_squaring-abs.html</a></p>

<p>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.</p>

CC BY-SA 3.0
2018-04-28T15:04:42.373Z
2018-04-28T15:04:42.373Z
Ryan Williams
<p>(This is a bit of follow-up to <a href="https://cstheory.stackexchange.com/posts/comments/93266">https://cstheory.stackexchange.com/posts/comments/93266</a> but is a distinct enough question I though it should be on its own.)</p>

<p>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.</p>

<p>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.</p>

<p>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).</p>

<p>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?</p>

CC BY-SA 3.0
2018-04-27T11:20:02.130Z
Here is a paper using replacement products instead of zig-zag: https://eccc.weizmann.ac.il/report/2016/144/
Emil Jeřábek
CC BY-SA 3.0
2018-04-27T11:51:56.543Z
Emil, I think you should make that an answer.
Jan Johannsen
CC BY-SA 3.0
2018-04-27T18:22:05.833Z
@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.)
Emil Jeřábek
CC BY-SA 3.0
2018-04-27T23:27:07.067Z
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.
Alex Meiburg
CC BY-SA 3.0
2018-04-28T16:16:41.280Z
The proof of Reingold's theorem in Arora & Barak's book uses the replacement product.
didest
CC BY-SA 3.0
2018-04-30T08:32:39.437Z
The journal version of Reingold's paper (JACM 2008) explicitly discusses the use of the replacement product.
András Salamon
CC BY-SA 3.0
2018-04-30T18:56:27.237Z
Thank you Diego and @AndrásSalamon especially, I wasn't aware that the version of Reingold's paper I had read wasn't the same as the journal version.
Alex Meiburg
<graph-theory><expanders><logspace>
Can $L=SL$ be shown with the replacement product instead of the zig-zag product?
Alex Meiburg
# Can $L=SL$ be shown with the replacement product instead of the zig-zag product?

(Asked by: username_0 on 2018-04-27)

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

**Tags:** graph-theory, expanders, logspace

> **Comments:**
> **username_1**: Here is a paper using replacement products instead of zig-zag: https://eccc.weizmann.ac.il/report/2016/144/  
> **username_2**: Emil, I think you should make that an answer.  
> **username_1**: @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.)  
> **username_0**: 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.  
> **username_3**: The proof of Reingold's theorem in Arora & Barak's book uses the replacement product.  
> **username_4**: The journal version of Reingold's paper (JACM 2008) explicitly discusses the use of the replacement product.  
> **username_0**: Thank you Diego and @AndrásSalamon especially, I wasn't aware that the version of Reingold's paper I had read wasn't the same as the journal version.  

---

## 1 answers

### Answer by username_5 on 2018-04-28. Score: 4 | Accepted answer

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.


---

