Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SPACE-BOUNDED COMPUTATION:
Reports tagged with Space-bounded computation:
TR20-026 | 25th February 2020
Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

#### 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\cdot ... more >>>

ISSN 1433-8092 | Imprint