EXPANDER GRAPHS AND THEIR APPLICATIONS 447 discuss our problem.Let {0,1]*denote the set of all finite binary strings.Then a language CC {0,1]*is in the class RP if there exists a randomized algorithm A with a polynomial (in running time such that if x C,then A(z,r)=1 (with certainty),whereas if x C,the probability of A(z,r)=1 is smaller than 1/16.(The definition remains unchanged with any constant 1 that we choose. The constant 1/16 was chosen for notational convenience.)Note again that r is a uniformly chosen random string of k bits,with k polynomially dependent on the length of the input z.In this case we say that C{0,1)*has a(1-sided error) randomized polynomial time membership algorithm. Problem 1.7 (Saving Random Bits).Assume that C {0,1)*has a (1-sided error)randomized polynomial time membership algorithm.How many random bits are needed in order to reduce the probability of error to be <e?(Note that we seek a bound that should apply to every input.) 1.2.Magical graphs.In the previous section we presented three seemingly un- related problems.We now introduce a new object:a "Magical Graph"that will enable us to solve all these problems.This object exhibits an "expansion"property (a "combinatorial isoperimetric inequality")to fit our three applications. Definition 1.8 (Magical Graph).Let G=(L,R,E)be a bipartite graph.The vertex set consists of L and R,two disjoint subsets,henceforth the left and right vertex sets.We say that G is an (n,m;d)-magical graph if L=n,R=m,and every left vertex has d neighbors and the following two properties hold(where I(S) denotes the set of neighbors of a set S in G): ()T(Sl≥g.IS]for every SCL with S]≤品 (2)T(Sl≥S]for every S≤L with0a<lS≤受 As observed by Pinsker Pin73](for other but related expansion properties),such graphs exist.The proof is by a probabilistic argument and it implies that,in fact, most graphs are magical Lemma 1.9.There erists a constant no such that for every d 32 and n no.m 3n/4 there erists an (n,m;d)-magical graph. Proof.Let G be a random bipartite graph with n vertices on the left and m vertices on the right,where each left vertex connects to a randomly chosen set of d vertices on the right.We claim that with high probability G is a magical graph.We start by proving that the first property holds with high probability. Let S_L have cardinality s=lS≤品，and let T∈R have cardinality t<Let Xs.r be an indicator random variable for the event that all the edges from S go to T.It is clear that if Xs.r=0,where the sum is over all choices of S and T as above,then the first property holds.The probability of the event Xs.r is (t/m)sd,and therefore using a union bound and the inequalityEXPANDER GRAPHS AND THEIR APPLICATIONS 447 discuss our problem. Let {0, 1}∗ denote the set of all finite binary strings. Then a language L⊆{0, 1}∗ is in the class RP if there exists a randomized algorithm A with a polynomial (in |x|) running time such that if x ∈ L, then A(x, r)=1 (with certainty), whereas if x /∈ L, the probability of A(x, r) = 1 is smaller than 1/16. (The definition remains unchanged with any constant < 1 that we choose. The constant 1/16 was chosen for notational convenience.) Note again that r is a uniformly chosen random string of k bits, with k polynomially dependent on the length |x| of the input x. In this case we say that L⊆{0, 1}∗ has a (1-sided error) randomized polynomial time membership algorithm. Problem 1.7 (Saving Random Bits). Assume that L⊆{0, 1}∗ has a (1-sided error) randomized polynomial time membership algorithm. How many random bits are needed in order to reduce the probability of error to be ≤  ? (Note that we seek a bound that should apply to every input.) 1.2. Magical graphs. In the previous section we presented three seemingly un￾related problems. We now introduce a new object: a “Magical Graph” that will enable us to solve all these problems. This object exhibits an “expansion” property (a “combinatorial isoperimetric inequality”) to fit our three applications. Definition 1.8 (Magical Graph). Let G = (L, R, E) be a bipartite graph. The vertex set consists of L and R, two disjoint subsets, henceforth the left and right vertex sets. We say that G is an (n,m; d)-magical graph if |L| = n, |R| = m, and every left vertex has d neighbors and the following two properties hold (where Γ(S) denotes the set of neighbors of a set S in G): (1) |Γ(S)| ≥ 5d 8 · |S| for every S ⊆ L with |S| ≤ n 10d . (2) |Γ(S)|≥|S| for every S ⊆ L with n 10d < |S| ≤ n 2 . As observed by Pinsker [Pin73] (for other but related expansion properties), such graphs exist. The proof is by a probabilistic argument and it implies that, in fact, most graphs are magical. Lemma 1.9. There exists a constant n0 such that for every d ≥ 32 and n ≥ n0, m ≥ 3n/4 there exists an (n,m; d)-magical graph. Proof. Let G be a random bipartite graph with n vertices on the left and m vertices on the right, where each left vertex connects to a randomly chosen set of d vertices on the right. We claim that with high probability G is a magical graph. We start by proving that the first property holds with high probability. Let S ⊆ L have cardinality s = |S| ≤ n 10d , and let T ⊆ R have cardinality t = |T| < 5ds 8 . Let XS,T be an indicator random variable for the event that all the edges from S go to T. It is clear that if
XS,T = 0, where the sum is over all choices of S and T as above, then the first property holds. The probability of the event XS,T is (t/m)sd, and therefore using a union bound and the inequality