454 SHLOMO HOORY,NATHAN LINIAL,AND AVI WIGDERSON Theorem2.4.Let G be a d-regular graph with spectrum入1≥·≥入n.Then d-也<h(G)≤V2dd- 2 This theorem is due to Cheeger Che70 and Buser Bus82 in the continuous case(see Section 4 for more on this).In the discrete case,it was proved by Dodz- iuk [Dod84]and independently by Alon-Milman [AM85]and by Alon [Alo86].More concretely we see that d-A2,also known as the Spectral Gap,provides an esti- mate on the expansion of a graph.In particular,a d-regular graph has an expansion ratio h(G)bounded away from zero iff its spectral gap d-A2 is bounded away from zero.The following lemma shows that a small second eigenvalue in a graph implies that its edges are "spread out",a hallmark of random graphs. 2.4.The Expander Mixing Lemma.Given a d-regular graph G with n vertices, we denote =A(G)=max(A2l,Anl).In words,A is the largest absolute value of an eigenvalue other than A1=d.The following useful bound,observed by several researchers,probably appeared in print first in [AC89] Lemma 2.5(Expander Mixing Lemma).Let G be a d-regular graph with n vertices and set入=λ(G).Then for all S,TcV: IE(s,T)1-ds ≤λvST. n A word of interpretation is in place here.The left-hand side measures the de- viation between two quantities:one is E(S,T),the number of edges between the two sets;the other is the expected number of edges between S and T in a random graph of edge density d/n,namely dlST/n.A small A (or large spectral gap) implies that this deviation (or discrepancy as it is sometimes called)is small,so the graph is nearly random in this sense. When the spectral gap of G is much smaller than d,the upper and lower bounds in Theorem 2.4 differ substantially.This makes one wonder whether the spectral gap can be captured more tightly by some combinatorial invariant of the graph.A positive answer,and a converse to the Expander Mixing Lemma,was found recently by Bilu and Linial BL].We will not prove this result here. Lemma 2.6(Converse of the Expander Mixing Lemma [BL]).Let G be a d-regular graph and suppose that 1E(s,1T1-SI四 ≤pWST, n holds for every two disjoint sets S,T and for some positive p.Then A<O(p.(1+ log(d/p))).The bound is tight. Proof of the Expander Miring Lemma.Let 1s and Ir be the characteristic vectors of S and T(i.e.,the v-th coordinate of the vector 1s is 1 if v E S and zero otherwise). Expand these vectors in the orthonormal basis of eigenvectors v1,...,Un,viz.,1s ∑iQivi and IT=∑jfv:Recall that vi=l/W元.Then E(S,T)=1sAlr =(iaivi)A(jBjvj)
454 SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON Theorem 2.4. Let G be a d-regular graph with spectrum λ1 ≥···≥ λn. Then d − λ2 2 ≤ h(G) ≤ 2d(d − λ2). This theorem is due to Cheeger [Che70] and Buser [Bus82] in the continuous case (see Section 4 for more on this). In the discrete case, it was proved by Dodziuk [Dod84] and independently by Alon-Milman [AM85] and by Alon [Alo86]. More concretely we see that d − λ2, also known as the Spectral Gap, provides an estimate on the expansion of a graph. In particular, a d-regular graph has an expansion ratio h(G) bounded away from zero iff its spectral gap d−λ2 is bounded away from zero. The following lemma shows that a small second eigenvalue in a graph implies that its edges are “spread out”, a hallmark of random graphs. 2.4. The Expander Mixing Lemma. Given a d-regular graph G with n vertices, we denote λ = λ(G) = max(|λ2|, |λn|). In words, λ is the largest absolute value of an eigenvalue other than λ1 = d. The following useful bound, observed by several researchers, probably appeared in print first in [AC89]. Lemma 2.5 (Expander Mixing Lemma). Let G be a d-regular graph with n vertices and set λ = λ(G). Then for all S, T ⊆ V : |E(S, T)| − d|S||T| n ≤ λ |S||T|. A word of interpretation is in place here. The left-hand side measures the deviation between two quantities: one is |E(S, T)|, the number of edges between the two sets; the other is the expected number of edges between S and T in a random graph of edge density d/n, namely d|S||T|/n. A small λ (or large spectral gap) implies that this deviation (or discrepancy as it is sometimes called) is small, so the graph is nearly random in this sense. When the spectral gap of G is much smaller than d, the upper and lower bounds in Theorem 2.4 differ substantially. This makes one wonder whether the spectral gap can be captured more tightly by some combinatorial invariant of the graph. A positive answer, and a converse to the Expander Mixing Lemma, was found recently by Bilu and Linial [BL]. We will not prove this result here. Lemma 2.6 (Converse of the Expander Mixing Lemma [BL]). Let G be a d-regular graph and suppose that |E(S, T)| − d|S||T| n ≤ ρ |S||T|, holds for every two disjoint sets S, T and for some positive ρ. Then λ ≤ O(ρ · (1 + log(d/ρ))). The bound is tight. Proof of the Expander Mixing Lemma. Let 1S and 1T be the characteristic vectors of S and T (i.e., the v-th coordinate of the vector 1S is 1 if v ∈ S and zero otherwise). Expand these vectors in the orthonormal basis of eigenvectors v1, ··· , vn, viz., 1S = Σiαivi and 1T = Σjβjvj . Recall that v1 = 1/ √n. Then |E(S, T)| = 1SA1T = (Σiαivi)A(Σjβjvj )
EXPANDER GRAPHS AND THEIR APPLICATIONS 455 Since thev;are orthonormal eigenvectors,this equals Since =(1s, =只，a=只amdh=d 1ES,T1=dS☒+路2AyaA. By the definition of A: ES,T川-dS☐|=1路2Aa4≤g-2lAa4≤Ag-2la n Finally,by Cauchy-Schwartz: IE(S,T)1-dsl ≤λa2ll2=I1s2l1rl2=λV1ST 口 In what follows,it is sometimes convenient to consider the normalized second eigenvalue A(G)/d.A d-regular graph G on n vertices is called an (n,d)-graph.It is an(n,d,a)-graph if A(G)<ad.Regular graphs with small a have a number of significant properties,some of which we collect below: An independent set in a graph is a set of vertices S,no two of which are adjacent,i.e.with E(S,S)=0.It is an immediate consequence of the Expander Mixing Lemma that an independent set in an(n,d,a)-graph has cardinality at most an. 。Ak-coloring of a graph G=(W,E)is a mapping c:V→{1，，k}, such that c(x)c(y)for any two adjacent vertices z,y.The chromatic number of G,denoted x(G),is the smallest k for which G has a k-coloring. The set c-(j)is an independent set in G for every k >j>1.Consequently, X(G)>1/a for an (n,d,a)-graph G. The distance dc(r,y)between vertices x and y in a graph G=(V,E) is the length of the shortest path between them.The diameter of G is defined as max,.ydc(x,y).Also B(x,r）={ldc(x,y）≤r}is the ball of radius r around r.We claim that an (n,d,a)-graph G has diameter O(logn).That certainly follows if we show that B(x,r)>n/2 for every vertex z and some r<O(logn).This in turn follows from the expansion properties of G.That is,we show that |B(z,r+1)>(1+e)B(r,r)|for some fixed e>0 as long as |B(,r)<n/2.The Expander Mixing Lemma implies that E(S,S)/S<d.(S/n +a)for every set S.Therefore, E(S,S)/S]d.((1-a)-Sl/n).But S has at least |E(S,S)l/d neighbors outside itself,so the claim follows with e=1/2-a. 2.5.How big can the spectral gap be?The question in the title has to be qualified,since the answer depends on the relationship between d and n.We are mostly interested in d fixed and large n.To illustrate how things may differ when d grows with n,consider the complete graph on n vertices Kn where every two vertices are adjacent and so d=n-1.Clearly the adjacency matrix of Kn is J-I where/is the all-ones matrix and I=In is the identity matrix.The spectrum of Knis[n-1,-1,-1,…,-1].and入=1. For the range we are interested in,n>d,the question was answered by N.Alon and R.Boppana (see A.Nilli [Nil91]):
EXPANDER GRAPHS AND THEIR APPLICATIONS 455 Since the vi are orthonormal eigenvectors, this equals Σiλiαiβi. Since α1 = 1S, √ 1 n = |S| √n , β1 = |T| √n , and λ1 = d: |E(S, T)| = d |S||T| n + Σn i=2λiαiβi. By the definition of λ: |E(S, T)| − d |S||T| n = |Σn i=2λiαiβi| ≤ Σn i=2|λiαiβi| ≤ λΣn i=2|αiβi|. Finally, by Cauchy-Schwartz: |E(S, T)| − d |S||T| n ≤ λα2β2 = λ1S21T 2 = λ |S||T|. In what follows, it is sometimes convenient to consider the normalized second eigenvalue λ(G)/d. A d-regular graph G on n vertices is called an (n,d)-graph. It is an (n, d, α)-graph if λ(G) ≤ αd. Regular graphs with small α have a number of significant properties, some of which we collect below: • An independent set in a graph is a set of vertices S, no two of which are adjacent, i.e. with |E(S, S)| = 0. It is an immediate consequence of the Expander Mixing Lemma that an independent set in an (n, d, α)-graph has cardinality at most αn. • A k-coloring of a graph G = (V,E) is a mapping c : V → {1,...,k}, such that c(x) = c(y) for any two adjacent vertices x, y. The chromatic number of G, denoted χ(G), is the smallest k for which G has a k-coloring. The set c−1(j) is an independent set in G for every k ≥ j ≥ 1. Consequently, χ(G) ≥ 1/α for an (n, d, α)-graph G. • The distance dG(x, y) between vertices x and y in a graph G = (V,E) is the length of the shortest path between them. The diameter of G is defined as maxx,y dG(x, y). Also B(x, r) = {y|dG(x, y) ≤ r} is the ball of radius r around x. We claim that an (n, d, α)-graph G has diameter O(log n). That certainly follows if we show that |B(x, r)| > n/2 for every vertex x and some r ≤ O(log n). This in turn follows from the expansion properties of G. That is, we show that |B(x, r + 1)| ≥ (1 + )|B(x, r)| for some fixed > 0 as long as |B(x, r)| ≤ n/2. The Expander Mixing Lemma implies that |E(S, S)|/|S| ≤ d · (|S|/n + α) for every set S. Therefore, |E(S, S)|/|S| ≥ d·((1−α)−|S|/n). But S has at least |E(S, S)|/d neighbors outside itself, so the claim follows with = 1/2 − α. 2.5. How big can the spectral gap be? The question in the title has to be qualified, since the answer depends on the relationship between d and n. We are mostly interested in d fixed and large n. To illustrate how things may differ when d grows with n, consider the complete graph on n vertices Kn where every two vertices are adjacent and so d = n −1. Clearly the adjacency matrix of Kn is J −I where J is the all-ones matrix and I = In is the identity matrix. The spectrum of Kn is [n − 1, −1, −1, ··· , −1]. and λ = 1. For the range we are interested in, n d, the question was answered by N. Alon and R. Boppana (see A. Nilli [Nil91]):
456 SHLOMO HOORY,NATHAN LINIAL,AND AVI WIGDERSON Theorem 2.7 (Alon-Boppana).For every(n,d)-graph, λ≥2vd-1-om(1). The on(1)term is a quantity that tends to zero for every fixed d as n-oo. More on this and a proof of this theorem appear in Section 5.Here is a very easy but somewhat weaker statement: Claim 2.8.For every (n,d)-graph G, 入≥Vd.(1-on(1) Proof.Let A be the adjacency matrix of G.It is not hard to see that trace(A)is the number of all walks of length k in G that start and end in the same vertex.In particular,all the diagonal entries in A2 are d.(Just move back and forth along any edge incident to the vertex in question.)Consequently,trace(A2)>nd.On the other hand. trace((42)=∑X号≤d2+(n-1)A2. It follows that 2d.,as claimed. 口 2.6.Four perspectives on expansion and how they compare.We are now in a position to offer the reader a broader view of some of the main questions in the field.Expansion is defined in combinatorial terms and,as we shall see.this definition comes in several different flavors.This is closely related to the spectral theory of graphs.Finally,rapidly mixing random walks provide a probabilistic perspective. In each of these three frameworks we consider mostly four types of questions: Extremal:How large/small can the pertinent expansion parameters be? Typical:How are these parameters distributed over random graphs? Explicit construction:Can one construct graphs for which these param- eters (nearly)attain their optimum? Algorithmic:Given a graph,can you efficiently evaluate/estimate its expansion parameters? It then becomes natural to consider some comparative problems:What can you conclude,say,about combinatorial-type expansion parameters from spectral information,etc.? Here are some pointers to the present article where we either explain what is known about such question or provide some further references to the relevant lit- erature. 2.6.1.Ertremal problems.Here the most satisfactory answer comes from the spec- tral realm.The Alon-Boppana Theorem 5.3 tells us precisely how large the spectral gap can be in an (n,d)-graph. The largest edge expansion h(G)of an (n,d)-graph G is at most d/2-cvd for every d>3 and sufficiently large n,where c >0 is an absolute constant.This result is tight up to the value of c;see subsection 5.1.1.More interesting(and often more difficult)questions concern the expansion of smaller sets in the graph.Some discussion of this problem is to be found in Section 5 and subsection 4.6
456 SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON Theorem 2.7 (Alon-Boppana). For every (n,d)-graph, λ ≥ 2 √ d − 1 − on(1). The on(1) term is a quantity that tends to zero for every fixed d as n → ∞. More on this and a proof of this theorem appear in Section 5. Here is a very easy but somewhat weaker statement: Claim 2.8. For every (n,d)-graph G, λ ≥ √ d · (1 − on(1)). Proof. Let A be the adjacency matrix of G. It is not hard to see that trace(Ak) is the number of all walks of length k in G that start and end in the same vertex. In particular, all the diagonal entries in A2 are ≥ d. (Just move back and forth along any edge incident to the vertex in question.) Consequently, trace(A2) ≥ nd. On the other hand, trace(A2) = i λ2 i ≤ d2 + (n − 1)λ2. It follows that λ2 ≥ d · n−d n−1 , as claimed. 2.6. Four perspectives on expansion and how they compare. We are now in a position to offer the reader a broader view of some of the main questions in the field. Expansion is defined in combinatorial terms and, as we shall see, this definition comes in several different flavors. This is closely related to the spectral theory of graphs. Finally, rapidly mixing random walks provide a probabilistic perspective. In each of these three frameworks we consider mostly four types of questions: • Extremal: How large/small can the pertinent expansion parameters be? • Typical: How are these parameters distributed over random graphs? • Explicit construction: Can one construct graphs for which these parameters (nearly) attain their optimum? • Algorithmic: Given a graph, can you efficiently evaluate/estimate its expansion parameters? It then becomes natural to consider some comparative problems: What can you conclude, say, about combinatorial-type expansion parameters from spectral information, etc.? Here are some pointers to the present article where we either explain what is known about such question or provide some further references to the relevant literature. 2.6.1. Extremal problems. Here the most satisfactory answer comes from the spectral realm. The Alon-Boppana Theorem 5.3 tells us precisely how large the spectral gap can be in an (n,d)-graph. The largest edge expansion h(G) of an (n,d)-graph G is at most d/2 − c √ d for every d ≥ 3 and sufficiently large n, where c > 0 is an absolute constant. This result is tight up to the value of c; see subsection 5.1.1. More interesting (and often more difficult) questions concern the expansion of smaller sets in the graph. Some discussion of this problem is to be found in Section 5 and subsection 4.6
EXPANDER GRAPHS AND THEIR APPLICATIONS 457 2.6.2.Tupical behavior.Here the situation reverses.It is relatively not hard to analyze the (vertex/edge)expansion in random graphs by methods similar to those used in subsection 1.2.See subsection 4.6 for more details. The typical behavior of the spectrum is harder to understand,and Section 7 is dedicated to an exposition of this fascinating story and the still lingering mysteries. 2.6.3.Explicit constructions.We have already mentioned the Margulis construc- tion to which Section 8 is dedicated.The so-called Ramanujan Graphs due to Lubotzky-Phillips-Sarnak LPS88]and Margulis Mar88]are mentioned briefly in subsection 5.3,but are otherwise not discussed at depth here.We do survey some more combinatorial approaches to the problem,viz.subsection 6.4 and Section 11. Direct estimates of the expansion,even for specific families of graphs,are even harder to come by and [LL06]is one of very few exceptions.In fact,the following question is quite nontrivial:Find explicit constructions of graphs in which small sets of vertices expand well.We will have quite a bit to say about this problem in Section 10. 2.6.4.Algorithms.The exact determination of h(G),given G,is difficult (co-NP- hard)[BKV81].This fact and the approximate version of the problem are briefly discussed in subsection 13.5.Likewise,we lack good estimates for the vertex isoperi- metric parameter of a given graph or for the edge expansion of sets of a given size in a graph.These are among the most significant open questions in the theory. On the other hand,standard algorithms in linear algebra can be used to efficiently compute the spectrum of a given graph.For the analogous problem in the context of random walks see subsection 3.1.2. 2.6.5.Comparisons.As mentioned above,for random graphs,expansion is more accessible than spectral gap.On the other hand,eigenvalues are easily computable, while expansion is not.It is interesting to ask how well one theory reflects on the other when we seek(nearly)optimal graphs.Graphs with very large spectral gap are very good expanders:When A=o(d),the lower bound in Theorem 2.4 yields h(G)>(-o(1))d.On the other hand,for d large,an (n,d)-graph G can have h(G)>(d)while the spectral gap is small.Here is an illustration of how this can happen:Pick a small 6 >0 and construct an (n,(6.d))-graph G with h(G)=(6.d) Now add to it a collection of disjoint cliques of size (1-6)d+1 each.Clearly h(G) does not decrease,but the spectral gap is at most od. Another interesting example can be obtained by considering the line graph H of an (n,d)-graph G that is a good expander.The vertex set of H is the edge set of G,and two vertices in H are adjacent iff the corresponding edges are incident in G.The graph H is an(4,2d-2)-graph.Its second eigenvalue is easily seen to be >(1-o(1))d,but if G has a large expansion ratio,then so does H. Finally,we mention that Lemma 2.6 shows the near equivalence of discrepancy and spectral gap. Connections with rapid mixing of random walks are discussed in subsection 3.1
EXPANDER GRAPHS AND THEIR APPLICATIONS 457 2.6.2. Typical behavior. Here the situation reverses. It is relatively not hard to analyze the (vertex/edge) expansion in random graphs by methods similar to those used in subsection 1.2. See subsection 4.6 for more details. The typical behavior of the spectrum is harder to understand, and Section 7 is dedicated to an exposition of this fascinating story and the still lingering mysteries. 2.6.3. Explicit constructions. We have already mentioned the Margulis construction to which Section 8 is dedicated. The so-called Ramanujan Graphs due to Lubotzky-Phillips-Sarnak [LPS88] and Margulis [Mar88] are mentioned briefly in subsection 5.3, but are otherwise not discussed at depth here. We do survey some more combinatorial approaches to the problem, viz. subsection 6.4 and Section 11. Direct estimates of the expansion, even for specific families of graphs, are even harder to come by and [LL06] is one of very few exceptions. In fact, the following question is quite nontrivial: Find explicit constructions of graphs in which small sets of vertices expand well. We will have quite a bit to say about this problem in Section 10. 2.6.4. Algorithms. The exact determination of h(G), given G, is difficult (co-NPhard) [BKV81]. This fact and the approximate version of the problem are briefly discussed in subsection 13.5. Likewise, we lack good estimates for the vertex isoperimetric parameter of a given graph or for the edge expansion of sets of a given size in a graph. These are among the most significant open questions in the theory. On the other hand, standard algorithms in linear algebra can be used to efficiently compute the spectrum of a given graph. For the analogous problem in the context of random walks see subsection 3.1.2. 2.6.5. Comparisons. As mentioned above, for random graphs, expansion is more accessible than spectral gap. On the other hand, eigenvalues are easily computable, while expansion is not. It is interesting to ask how well one theory reflects on the other when we seek (nearly) optimal graphs. Graphs with very large spectral gap are very good expanders: When λ = o(d), the lower bound in Theorem 2.4 yields h(G) ≥ ( 1 2 − o(1))d. On the other hand, for d large, an (n,d)-graph G can have h(G) ≥ Ω(d) while the spectral gap is small. Here is an illustration of how this can happen: Pick a small δ > 0 and construct an (n,(δ·d))-graph G with h(G) = Ω(δ·d). Now add to it a collection of disjoint cliques of size (1 − δ)d + 1 each. Clearly h(G) does not decrease, but the spectral gap is at most δd. Another interesting example can be obtained by considering the line graph H of an (n,d)-graph G that is a good expander. The vertex set of H is the edge set of G, and two vertices in H are adjacent iff the corresponding edges are incident in G. The graph H is an ( nd 2 , 2d − 2)-graph. Its second eigenvalue is easily seen to be ≥ (1 − o(1))d, but if G has a large expansion ratio, then so does H. Finally, we mention that Lemma 2.6 shows the near equivalence of discrepancy and spectral gap. Connections with rapid mixing of random walks are discussed in subsection 3.1
458 SHLOMO HOORY.NATHAN LINIAL.AND AVI WIGDERSON 3.Random walks on expander graphs A key property of the random walk on an expander graph is that it converges rapidly to its limit distribution.This fact has numerous important consequences at which we can only hint.In many theoretical and practical computational problems in science and engineering it is necessary to draw samples from some distribution F on a (usually finite but huge)set V.Such problems are often solved by so-called "Monte-Carlo"algorithms.One considers a graph G on vertex set V so that the limit distribution of the random walk on G is F.A clever choice of G can guarantee that(i)it is feasible to efficiently simulate this random walk and(ii)the distribution induced on V by the walk converges rapidly to F.Among the fields where this methodology plays an important role are Statistical Physics,Computational Group Theory and Combinatorial Optimization.We should mention approximation algo- rithms for the permanence of nonnegative matrices [JSV04]and for the volume of convex bodies in high dimension [Sim03]as prime examples of the latter.Excellent surveys on the subject are JS96,Jer03.As we briefly mention in subsection 4.5. some of this theory extends to the more general context of time-reversible Markov Chains [LW98,MT]. The main principle behind the topics we survey here is that the set of vertices visited by a length t random walk on an expander graph "looks like"(in some respects)a set of t vertices sampled uniformly and independently.The compu- tational significance of this is that the number of random bits required in order to generate a length t walk on a(constant-degree)graph is significantly smaller than the number of random bits that are needed in order to independently sample t random vertices.We exhibit two applications of this idea:(i)a randomness- efficient error reduction procedure for randomized algorithms,and (ii)a strong hardness-of-approximation result for the maximum clique problem.Other compu- tational applications of these ideas that we will not go into include derandomization of probabilistic space-bounded algorithms (see e.g.Nisan-Zuckerman [NZ96]and mpagliazzo-Nisan-Wigderson INW94) 3.1.Rapid mixing of walks.A walk on a graph G=(V,E)is a sequence of vertices v1,v2,...EV such that vi+i is a neighbor of vi for every index i.When vi+1 is selected uniformly at random from among vi's neighbors,independently for every i,this is called a random walk on G.We usually initiate this random process by selecting the first vertex v from some initial probability distribution mi on V.Clearly this induces a sequence of probability distributions m;on V so that the probability that vi=z EV equals mi(z)for every i and x.It is well known that for every finite connected nonbipartite graph G,the distributions mi converge to a limit,or stationary,distribution.Moreover,it is easy to see that if G is regular, then this distribution is the uniform distribution on V. This subsection deals with the speed of this convergence.There are several interesting ways to measure the distance between mi and the limit distribution,and we will consider several norms and entropy measures.The main thrust is that in expanders the distance to the limit shrinks substantially with every step of the random walk and that this condition characterizes expander graphs.We now make this statement quantitative.We start with some definitions and notations
458 SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON 3. Random walks on expander graphs A key property of the random walk on an expander graph is that it converges rapidly to its limit distribution. This fact has numerous important consequences at which we can only hint. In many theoretical and practical computational problems in science and engineering it is necessary to draw samples from some distribution F on a (usually finite but huge) set V . Such problems are often solved by so-called “Monte-Carlo” algorithms. One considers a graph G on vertex set V so that the limit distribution of the random walk on G is F. A clever choice of G can guarantee that (i) it is feasible to efficiently simulate this random walk and (ii) the distribution induced on V by the walk converges rapidly to F. Among the fields where this methodology plays an important role are Statistical Physics, Computational Group Theory and Combinatorial Optimization. We should mention approximation algorithms for the permanence of nonnegative matrices [JSV04] and for the volume of convex bodies in high dimension [Sim03] as prime examples of the latter. Excellent surveys on the subject are [JS96, Jer03]. As we briefly mention in subsection 4.5, some of this theory extends to the more general context of time-reversible Markov Chains [LW98, MT]. The main principle behind the topics we survey here is that the set of vertices visited by a length t random walk on an expander graph “looks like” (in some respects) a set of t vertices sampled uniformly and independently. The computational significance of this is that the number of random bits required in order to generate a length t walk on a (constant-degree) graph is significantly smaller than the number of random bits that are needed in order to independently sample t random vertices. We exhibit two applications of this idea: (i) a randomnessefficient error reduction procedure for randomized algorithms, and (ii) a strong hardness-of-approximation result for the maximum clique problem. Other computational applications of these ideas that we will not go into include derandomization of probabilistic space-bounded algorithms (see e.g. Nisan-Zuckerman [NZ96] and Impagliazzo-Nisan-Wigderson [INW94]). 3.1. Rapid mixing of walks. A walk on a graph G = (V,E) is a sequence of vertices v1, v2,... ∈ V such that vi+1 is a neighbor of vi for every index i. When vi+1 is selected uniformly at random from among vi’s neighbors, independently for every i, this is called a random walk on G. We usually initiate this random process by selecting the first vertex v1 from some initial probability distribution π1 on V . Clearly this induces a sequence of probability distributions πi on V so that the probability that vi = x ∈ V equals πi(x) for every i and x. It is well known that for every finite connected nonbipartite graph G, the distributions πi converge to a limit, or stationary, distribution. Moreover, it is easy to see that if G is regular, then this distribution is the uniform distribution on V . This subsection deals with the speed of this convergence. There are several interesting ways to measure the distance between πi and the limit distribution, and we will consider several norms and entropy measures. The main thrust is that in expanders the distance to the limit shrinks substantially with every step of the random walk and that this condition characterizes expander graphs. We now make this statement quantitative. We start with some definitions and notations