DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2025.40

Derandomized Squaring: An Analytical Insight into Its True Behavior

Authors: Gil Cohen, Itay Cohen, Gal Maor, and Yuval Peled

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

The notion of the derandomized square of two graphs, denoted as G s H, was introduced by Rozenman and Vadhan as they rederived Reingold’s Theorem, SL = 𝐋. This pseudorandom primitive, closely related to the Zig-Zag product, plays a crucial role in recent advancements on space-bounded derandomization. For this and other reasons, understanding the spectral expansion λ(G s H) becomes paramount. Rozenman and Vadhan derived an upper bound for λ(G s H) in terms of the spectral expansions of the individual graphs, λ(G) and λ(H). They also proved their bound is optimal if the only information incorporated to the bound is the spectral expansion of the two graphs. The objective of this work is to gain deeper insights into the behavior of derandomized squaring by taking into account the entire spectrum of H, where we focus on a vertex-transitive c-regular H. Utilizing deep results from analytic combinatorics, we establish a lower bound on λ(G s H) that applies universally to all graphs G. Our work reveals that the bound is the minimum value of the function d⋅ x - d(d-1)χ_x(H)/χ_x'(H) in the domain (c,∞), where χ_x(H) is the characteristic polynomial of the d-vertex graph H. This bound lies far below the known upper bound for λ(G s H) for most reasonable choices for H. Empirical evidence suggests that our lower bound is optimal. We support the tightness of our lower bound by showing that the bound is tight for a class of graphs which exhibit local behavior similar to a derandomized squaring operation with H. To this end, we make use of finite free probability theory. In our second result, we resolve an open question posed by Cohen and Maor (STOC 2023) and establish a lower bound for the spectral expansion of rotating expanders. These graphs are constructed by taking a random walk with vertex permutations occurring after each step. We prove that Cohen and Maor’s construction is essentially optimal. Unlike our results on derandomized squaring, the proof in this instance relies solely on combinatorial methods. The key insight lies in establishing a connection between random walks on graph products and the Fuss-Catalan numbers.

Cite as

Gil Cohen, Itay Cohen, Gal Maor, and Yuval Peled. Derandomized Squaring: An Analytical Insight into Its True Behavior. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2025.40,
  author =	{Cohen, Gil and Cohen, Itay and Maor, Gal and Peled, Yuval},
  title =	{{Derandomized Squaring: An Analytical Insight into Its True Behavior}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{40:1--40:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.40},
  URN =		{urn:nbn:de:0030-drops-226681},
  doi =		{10.4230/LIPIcs.ITCS.2025.40},
  annote =	{Keywords: Derandomized Squaring, Spectral Graph Theory, Analytic Combinatorics}
}

Document

DOI: 10.4230/LIPIcs.CCC.2023.8

Spectral Expanding Expanders

Authors: Gil Cohen and Itay Cohen

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract

Dinitz, Schapira, and Valadarsky [Dinitz et al., 2017] introduced the intriguing notion of expanding expanders - a family of expander graphs with the property that every two consecutive graphs in the family differ only on a small number of edges. Such a family allows one to add and remove vertices with only few edge updates, making them useful in dynamic settings such as for datacenter network topologies and for the design of distributed algorithms for self-healing expanders. [Dinitz et al., 2017] constructed explicit expanding-expanders based on the Bilu-Linial construction of spectral expanders [Bilu and Linial, 2006]. The construction of expanding expanders, however, ends up being of edge expanders, thus, an open problem raised by [Dinitz et al., 2017] is to construct spectral expanding expanders (SEE). In this work, we resolve this question by constructing SEE with spectral expansion which, like [Bilu and Linial, 2006], is optimal up to a poly-logarithmic factor, and the number of edge updates is optimal up to a constant. We further give a simple proof for the existence of SEE that are close to Ramanujan up to a small additive term. As in [Dinitz et al., 2017], our construction is based on interpolating between a graph and its lift. However, to establish spectral expansion, we carefully weigh the interpolated graphs, dubbed partial lifts, in a way that enables us to conduct a delicate analysis of their spectrum. In particular, at a crucial point in the analysis, we consider the eigenvectors structure of the partial lifts.

Cite as

Gil Cohen and Itay Cohen. Spectral Expanding Expanders. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2023.8,
  author =	{Cohen, Gil and Cohen, Itay},
  title =	{{Spectral Expanding Expanders}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.8},
  URN =		{urn:nbn:de:0030-drops-182780},
  doi =		{10.4230/LIPIcs.CCC.2023.8},
  annote =	{Keywords: Expanders, Normalized Random Walk, Spectral Analysis}
}

Search Results

Documents authored by Cohen, Itay

Derandomized Squaring: An Analytical Insight into Its True Behavior

Abstract

Cite as

Spectral Expanding Expanders

Abstract

Cite as

Thanks for your feedback!

Could not send message