期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-37
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 Oe(k log(N · wmax/wmin)) where wmax and wmin are the maximum and minimum edge weights in G, and produces a weighted graph H with Oe(n 1 2/k/ε2 ) expected edges that spectrally approximates G, in the sense of Spielmen and Teng [ST04], 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 [SS11] 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.
