Theory of Computing
-------------------
Title : Deterministic Approximation of Random Walks in Small Space
Authors : Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan
Volume : 17
Number : 4
Pages : 1-35
URL : http://www.theoryofcomputing.org/articles/v017a004
Abstract
--------
We give a deterministic, nearly logarithmic-space algorithm that given
an undirected multigraph $G$, a positive integer $r$, and a set $S$ of
vertices, approximates the conductance of $S$ in the $r$-step random
walk on $G$ to within a factor of $1+\epsilon$, where $\epsilon> 0$ is
an arbitrarily small constant. More generally, our algorithm computes
an $\epsilon$-spectral approximation to the normalized Laplacian of
the $r$-step walk.
Our algorithm combines the derandomized square graph operation
(Rozenman and Vadhan, RANDOM'05), which we recently used for solving
Laplacian systems in nearly logarithmic space (Murtagh et al.,
FOCS'17), with ideas from (Cheng et al., 2015) which gave an algorithm
that is time-efficient (while ours is space-efficient) and randomized
(while ours is deterministic) for the case of even $r$ (while ours
works for all $r$). Along the way, we provide some new results that
generalize technical machinery and yield improvements over previous
work. First, we obtain a nearly linear-time randomized algorithm for
computing a spectral approximation to the normalized Laplacian for odd
$r$. Second, we define and analyze a generalization of the
derandomized square for irregular multigraphs and for sparsifying the
product of two distinct multigraphs. As part of this generalization,
we also give a strongly explicit construction of expander graphs of
every size.
----------------
A conference version of this paper appeared in the Proceedings of
the 23rd International Conference on Randomization and Computation
(RANDOM 2019).