2026-07-22T00:15:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12446 2024-03-06T10:50:09Z ddc:004 open_access

Spectral Sparsification via Bounded-Independence Sampling Doron, Dean Murtagh, Jack Vadhan, Salil Zuckerman, David Spectral sparsification Derandomization Space complexity 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 Õ(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 Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dean Doron and Jack Murtagh and Salil Vadhan and David Zuckerman 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.39 urn:nbn:de:0030-drops-124462 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.39 eng https://creativecommons.org/licenses/by/3.0/legalcode