文章基本信息

标题：Spectral Sparsification via Bounded-Independence Sampling
本地全文：下载
作者：Dean Doron ; Jack Murtagh ; Salil Vadhan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：39:1-39:21
DOI：10.4230/LIPIcs.ICALP.2020.39
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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Ìf(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Ìf(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.
关键词：Spectral sparsification; Derandomization; Space complexity