  We give a deterministic, nearly logarithmic-space algorithm that given an
undirected graph $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, 2005), which we recently used for solving Laplacian systems in nearly
logarithmic space (Murtagh, Reingold, Sidford, and Vadhan, 2017), with ideas
from (Cheng, Cheng, Liu, Peng, and Teng, 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 graphs and for sparsifying the product of two
distinct graphs. As part of this generalization, we also give a strongly
explicit construction of expander graphs of every size.
