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.2021.33

Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract)

Authors: Edward Pyne and Salil Vadhan

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a weighted pseudorandom generator (WPRG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of WPRGs for ordered branching programs whose seed length has a better dependence on the error parameter ε than the classic PRG construction of Nisan (STOC 1990 and Combinatorica 1992). In this work, we give an explicit construction of WPRGs that achieve parameters that are impossible to achieve by a PRG. In particular, we construct a WPRG for ordered permutation branching programs of unbounded width with a single accept state that has seed length Õ(log^{3/2} n) for error parameter ε = 1/poly(n), where n is the input length. In contrast, recent work of Hoza et al. (ITCS 2021) shows that any PRG for this model requires seed length Ω(log² n) to achieve error ε = 1/poly(n). As a corollary, we obtain explicit WPRGs with seed length Õ(log^{3/2} n) and error ε = 1/poly(n) for ordered permutation branching programs of width w = poly(n) with an arbitrary number of accept states. Previously, seed length o(log² n) was only known when both the width and the reciprocal of the error are subpolynomial, i.e. w = n^{o(1)} and ε = 1/n^{o(1)} (Braverman, Rao, Raz, Yehudayoff, FOCS 2010 and SICOMP 2014). The starting point for our results are the recent space-efficient algorithms for estimating random-walk probabilities in directed graphs by Ahmadenijad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), which are based on spectral graph theory and space-efficient Laplacian solvers. We interpret these algorithms as giving WPRGs with large seed length, which we then derandomize to obtain our results. We also note that this approach gives a simpler proof of the original result of Braverman, Cohen, and Garg, as independently discovered by Cohen, Doron, Renard, Sberlo, and Ta-Shma (these proceedings).

Cite as

Edward Pyne and Salil Vadhan. Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract). In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{pyne_et_al:LIPIcs.CCC.2021.33,
  author =	{Pyne, Edward and Vadhan, Salil},
  title =	{{Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract)}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.33},
  URN =		{urn:nbn:de:0030-drops-143070},
  doi =		{10.4230/LIPIcs.CCC.2021.33},
  annote =	{Keywords: pseudorandomness, space-bounded computation, spectral graph theory}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2021.7

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Authors: William M. Hoza, Edward Pyne, and Salil Vadhan

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract

We prove that the Impagliazzo-Nisan-Wigderson [Impagliazzo et al., 1994] pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of Õ(log d + log n ⋅ log(1/ε)), assuming the program has only one accepting vertex in the final layer. Here, n is the length of the program, d is the degree (equivalently, the alphabet size), and ε is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length Ω(n log d) to fool such unbounded-width programs. Thus, this is an unusual case where an explicit construction is "better than random." Except when the program’s width w is very small, this is an improvement over prior work. For example, when w = poly(n) and d = 2, the best prior PRG for permutation branching programs was simply Nisan’s PRG [Nisan, 1992], which fools general ordered branching programs with seed length O(log(wn/ε) log n). We prove a seed length lower bound of Ω̃(log d + log n ⋅ log(1/ε)) for fooling these unbounded-width programs, showing that our seed length is near-optimal. In fact, when ε ≤ 1/log n, our seed length is within a constant factor of optimal. Our analysis of the INW generator uses the connection between the PRG and the derandomized square of Rozenman and Vadhan [Rozenman and Vadhan, 2005] and the recent analysis of the latter in terms of unit-circle approximation by Ahmadinejad et al. [Ahmadinejad et al., 2020].

Cite as

William M. Hoza, Edward Pyne, and Salil Vadhan. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hoza_et_al:LIPIcs.ITCS.2021.7,
  author =	{Hoza, William M. and Pyne, Edward and Vadhan, Salil},
  title =	{{Pseudorandom Generators for Unbounded-Width Permutation Branching Programs}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.7},
  URN =		{urn:nbn:de:0030-drops-135464},
  doi =		{10.4230/LIPIcs.ITCS.2021.7},
  annote =	{Keywords: Pseudorandom generators, permutation branching programs}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.39

Spectral Sparsification via Bounded-Independence Sampling

Authors: Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph G on n vertices described by a binary string of length N, an integer k ≤ log n and an error parameter ε > 0, our algorithm runs in space Õ(k log(N w_max/w_min)) where w_max and w_min are the maximum and minimum edge weights in G, and produces a weighted graph H with Õ(n^(1+2/k)/ε²) edges that spectrally approximates G, in the sense of Spielmen and Teng [Spielman and Teng, 2004], up to an error of ε. Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastava’s effective resistance based edge sampling algorithm [Spielman and Srivastava, 2011] and uses results from recent work on space-bounded Laplacian solvers [Jack Murtagh et al., 2017]. In particular, we demonstrate an inherent tradeoff (via upper and lower bounds) between the amount of (bounded) independence used in the edge sampling algorithm, denoted by k above, and the resulting sparsity that can be achieved.

Cite as

Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman. Spectral Sparsification via Bounded-Independence Sampling. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 39:1-39:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.ICALP.2020.39,
  author =	{Doron, Dean and Murtagh, Jack and Vadhan, Salil and Zuckerman, David},
  title =	{{Spectral Sparsification via Bounded-Independence Sampling}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{39:1--39:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.39},
  URN =		{urn:nbn:de:0030-drops-124462},
  doi =		{10.4230/LIPIcs.ICALP.2020.39},
  annote =	{Keywords: Spectral sparsification, Derandomization, Space complexity}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2020.129

The Complexity of Verifying Loop-Free Programs as Differentially Private

Authors: Marco Gaboardi, Kobbi Nissim, and David Purser

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

We study the problem of verifying differential privacy for loop-free programs with probabilistic choice. Programs in this class can be seen as randomized Boolean circuits, which we will use as a formal model to answer two different questions: first, deciding whether a program satisfies a prescribed level of privacy; second, approximating the privacy parameters a program realizes. We show that the problem of deciding whether a program satisfies ε-differential privacy is coNP^#P-complete. In fact, this is the case when either the input domain or the output range of the program is large. Further, we show that deciding whether a program is (ε,δ)-differentially private is coNP^#P-hard, and in coNP^#P for small output domains, but always in coNP^{#P^#P}. Finally, we show that the problem of approximating the level of differential privacy is both NP-hard and coNP-hard. These results complement previous results by Murtagh and Vadhan [Jack Murtagh and Salil P. Vadhan, 2016] showing that deciding the optimal composition of differentially private components is #P-complete, and that approximating the optimal composition of differentially private components is in P.

Cite as

Marco Gaboardi, Kobbi Nissim, and David Purser. The Complexity of Verifying Loop-Free Programs as Differentially Private. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 129:1-129:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gaboardi_et_al:LIPIcs.ICALP.2020.129,
  author =	{Gaboardi, Marco and Nissim, Kobbi and Purser, David},
  title =	{{The Complexity of Verifying Loop-Free Programs as Differentially Private}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{129:1--129:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.129},
  URN =		{urn:nbn:de:0030-drops-125362},
  doi =		{10.4230/LIPIcs.ICALP.2020.129},
  annote =	{Keywords: differential privacy, program verification, probabilistic programs}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.42

Deterministic Approximation of Random Walks in Small Space

Authors: Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract

We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph G, a positive integer r, and a set S of vertices, approximates the conductance of S in the r-step random walk on G to within a factor of 1+epsilon, where epsilon>0 is an arbitrarily small constant. More generally, our algorithm computes an epsilon-spectral approximation to the normalized Laplacian of the r-step walk. Our algorithm combines the derandomized square graph operation [Eyal Rozenman and Salil Vadhan, 2005], which we recently used for solving Laplacian systems in nearly logarithmic space [Murtagh et al., 2017], with ideas from [Cheng et al., 2015], which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even r (while ours works for all r). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd r. Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.

Cite as

Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan. Deterministic Approximation of Random Walks in Small Space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 42:1-42:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{murtagh_et_al:LIPIcs.APPROX-RANDOM.2019.42,
  author =	{Murtagh, Jack and Reingold, Omer and Sidford, Aaron and Vadhan, Salil},
  title =	{{Deterministic Approximation of Random Walks in Small Space}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{42:1--42:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.42},
  URN =		{urn:nbn:de:0030-drops-112577},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.42},
  annote =	{Keywords: random walks, space complexity, derandomization, spectral approximation, expander graphs}
}

6 Search Results for "Murtagh, Jack"

Derandomized Squaring: An Analytical Insight into Its True Behavior

Abstract

Cite as

Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract)

Abstract

Cite as

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Abstract

Cite as

Spectral Sparsification via Bounded-Independence Sampling

Abstract

Cite as

The Complexity of Verifying Loop-Free Programs as Differentially Private

Abstract

Cite as

Deterministic Approximation of Random Walks in Small Space

Abstract

Cite as

Thanks for your feedback!

Could not send message