Section 10.1.1. Modern interest in expanders and their algorithmic uses goes back to the early 1980s, e.g. their use in parallel sorting networks by Ajtai et al [3], and was increased by Alon’s [29] graph-theoretic formulation of Cheeger’s inequality. The conference proceedings [157] provides an overview.
Edge-expansion, measured by parameters like at (10.2), is more relevant to random walk than vertex-expansion. Walters [334] compares definitions. What we call “expander” is often called bounded-degree expander.
Section 10.1.2. Ajtai et al [4], studying the “amplification of randomness” problems in section 10.4.1, was perhaps the first explicit use of random walk on expanders. In Theorem 10.1, the upper bounds on and go back to Chandra et al [85].
Section 10.1.3. With the failure of conjecture (10.9), the next natural conjecture is: on a -regular graph
It’s not clear whether such conjectures are worth pursuing.
On a not-necessarily-regular graph, Chung [95] studies the eigenvalues of the matrix defined by
(10.23) | |||||
In the regular case, is the -matrix of transition rates for the continuous-time random walk, and so Chung’s eigenvalues are identical to our continuous-time eigenvalues. In the non-regular case there is no simple probabilistic interpretation of and hence no simple probabilistic interpretation of results involving the relaxation time associated with .
Section 10.2.1. Chung [95] Chapter 3 gives more detailed results about diameter and eigenvalues. One can slightly sharpen the argument for Proposition 10.4 by using (10.11) and the analog of Chapter 4 Lemma 26 (yyy 10/11/94 version) in which the threshold for is set at . Such arguments give bounds closer to that of [95] Corollary 3.2: if is not complete then
Section 10.2.2. Chung [95] section 4.4 analyzes a somewhat related routing problem. Broder et al [68] analyze a dynamic version of path selection in expanders.
Section 10.3.1. Example 10.7 (union of sets) and the more general DNF counting problem were studied systematically by Karp et al [210]; see also [265] section 11.2.
The Solovay-Strassen test of primality depends on a certain property of the Jacobi symbol: see [265] section 14.6 for a proof of this property.
Section 10.4.1. Several other uses of random walks on expanders can be found in Ajtai et al [4], Cohen and Wigderson [97], Impagliazzo and Zuckerman [188].
Section 10.4.4. Tetali [327] discussions extensions of parts (a,b) of Proposition 10.10 to nonsymmetric cost matrices.
Section 10.5. More extensive treatments of approximate counting are in Sinclair [308] and Motwani and Raghavan [265] Chapter 12.
Jerrum et al [200] formalize a notion of self-reducibility and show that, under this condition, approximate counting can be performed in polynomial time iff approximately uniform sampling can. See Sinclair [308] section 1.4 for a nice exposition.
Abstractly, we are studying randomized algorithms which produce a random estimate of a numerical quantity (where measures the “size” of the problem) together with a rigorous bound of the form
Such a scheme is a FPRAS (fully polynomial randomized approximation scheme) if the cost of the algorithm is bounded by a polynomial in , and . Here the conclusion involving is what emerges from proofs using large deviation techniques.
Section 10.5.1. Other papers on the volume problem and the related problem of sampling from a log-concave distribution are Lovász and Simonovits [238], Applegate and Kannan [33], Dyer and Frieze [136], Lovász and Simonovits [239] and Frieze et al [158].
Section 10.5.2. In the background is the problem of approximating the permanent
of a non-negative matrix, where the sum is over all permutations . When is the adjacency matrix of a bipartite graph, per(A) is the number of perfect matchings. Approximate counting of perfect matchings is in principle similar to approximate counting of all matchings; one seeks to use the chain in section 10.5.2 restricted to , where is the set of matchings with exactly edges. But successful analysis of this chain requires that we have a dense graph, with minimum degree . Jerrum and Sinclair [196] gave the first analysis, using the Cheeger inequality and estimating expansion via distinguished paths. Sinclair [308] Chapter 3 and Motwani and Raghavan [265] Chapter 11 give more detailed expositions. Subsequently it was realized that using the distinguished paths technique directly to bound was more efficient. A more general setting is to seek to sample from the non-uniform distribution on matchings
for a parameter . The distinguished paths technique [197, 199] giving (10.22) works in this setting to give