Publications by Year: 2024

2024
Barak, Boaz, Yael Kalai, Ran Raz, Salil Vadhan, and Nisheeth Vishnoi. “On the Works of Avi Widgerson.” In The Abel Prize 2018-2022 (eds. Helge Holden and Ragni Piene). 2023rd ed. Springer, Cham, 2024. Publisher's VersionAbstract ArXiv 2023.pdf
Doron, Dean, Jack Murtagh, Salil Vadhan, and David Zuckerman. “Small-space spectral sparsification via bounded-independence sampling.” ACM Transactions on Computation Theory (2024). Publisher's VersionAbstract
Version History:
NB: Some earlier versions published as "Spectral sparsification via bounded-independence sampling".

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 \leq \log n \) and an error parameter \(\varepsilon > 0\), our algorithm runs in space \(\tilde{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 \(\tilde{O}(n^{1+2/k} / \varepsilon^2)\)expected edges that spectrally approximates \(G\), in the sense of Spielmen and Teng [ST04], up to an error of \(\varepsilon\).

Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastava's effective resistance based edge sampling algorithm [SS08] and uses results from recent work on space-bounded Laplacian solvers [MRSV17]. 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.

ECCC 2020.pdf ICALP 2020.pdf ACM 2023.pdf