A Blogscursion into the World of Expanders

Recap: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

2005-12-16T16:48:00.000-08:00

Recap: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

We are given an expander graph G.

We are interested in functions f:V->[-1, 1] and aim to calculate the
expectation E[f]. For this analysis we are given that E[f] = 0, but we can also consider estimating E[g] for functions g where
E[g] != 0. To do so let f = g - E[g], so that E[f] = 0.

We consider taking a sample W=(Y₁, ..., Y_k) of vertices of V. We consider three bounds:

Chernoff
e ^{( -γ^2 k/2.4)}

Walk on G (strong bound)
e ^{-γ^2 ε k/60}

Walk on G (weak bound)
((2/ε log 8/(γ ε)) e ^{-(γ^2 k ε^3)/(12(2 log 8/(γ ε)))}

In the first case, W is a random, independent sample, resulting in a trivial Chernoff bound.

In the second and third cases, W is a random walk on G.

Chernoff bound and the weak bound for the random walk.
The proof for the Chernoff bound uses Markov's inequality and other simple algebraic
manipulations to arrive at a point where the independence of the Y _i
can be used.

When W is a walk, we cannot use the independence of the Y _i, since the
Y _i are not independent. Instead we apply linear algebra to show
that a summation is bounded by a dot product, and then bound the dot product by
an algebraic expression. We minimize over an arbitrary constant t to get the desired bound.
We then boost this result by dividing the walk W into samples and applying the union bound.

Lastly, we consider another paper, A Simple Chernoff Bound for Random Walks on a Weighted Graph, by David Gillman. In this paper a walk is taken on a
weighted graph, and the objective is to estimate the weight of the vertices in A, where
A is a subset of V, by sampling
(the weight of a vertex is equal to the sum of the weights of its edges).

In the setting of the previous paper, it is as though f is being taken as a 0-1 function, 0 for the vertices not in A and 1 for the vertices in A.

The main result of the paper quantifies the rate convergence of estimates of the weight of A to the actual weight of A as the length of the sample walk increases.

Then we explore three approximation algorithms, the Standard Procedure, Aldous's Procedure, and
Aldous's Procedure with Statistical Technique. The Standard Procedure takes multiple walks, sampling the last vertex of each walk.
Aldous's Procedure takes a walk and samples every verex after a certain count.
Aldous's Procedure with statistical techniques runs Aldous's Procedure multiple times to get
more accurate results.

The paper shows that Aldous's Procedure with Statistical Technique always beats the Standard Procedure, as does Aldous's Procedure given certain conditions.

Recap: Expanders and Coding Theory

2005-12-12T22:10:00.000-08:00

We looked at applications of Expanders to Coding Theory and saw that they could be used to obtain efficient encoding and decoding algorithms, with good error-detection and recovery properties.

We first considered codes which used the adjacency matrix of a bipartite expander as the parity check matrix. The simple FLIP algorithm allowed us to decode from a constant fraction of errors in linear time. In this algorithm, vertices of the left partite set are labelled with the bits of the received word, and a vertex of the right partite set is satisfed if an even number of its neighbors are set to '1'. As long as any vertex on the left has more unsatisfied than satisfied neighbors, we flip the bit corresponding to that vertex.

A similar idea could be tried for efficient encoding, but in order to obtain a linear time algorithm, the adjacency matrix must be sparse. Codes with low-density generating matrices have poor error correcting capabilities, but Spielman showed that such codes could be used for error reduction. Using Spielman's error-reducing codes, we can inductively construct error-correcting codes which allow linear-time encoding.

Another use of expanders is in the algorithm of Alon, Bruck, Naor, Naor and Roth; their construction allows us to obtain linear-time encodable and decodable codes with very large minimum distance (and hence good error correction); the price we pay is a significantly increased alphabet size. Finally, we considered list decoding, in which we output all codewords (not just the nearest codeword) that are sufficiently close to the received word. The ABNNR construction allowed us to construct a (1,2,2)-list recoverable code: that is, if in the received codeword, we have a list of two possible symbols for each position of the codeword, we output each of the (at most 2) codewords that are compatible with all the lists. We also saw that a similar construction could be used to obtain list-decodable codes from list-recoverable codes.

Recap: The PCP Theorem by Gap Amplification

2005-12-10T19:19:00.000-08:00

The PCP theorem (almost) states this surprising property that given a proof of answer of some YES/NO problem, there is some scheme that checks just some constant pieces of the proof and decides whether the proof is correct or not, and this decision is with high probability a correct decision.

It is almost easily known that NP-hardness of GAP-3SAT problem is equivalent to correctness of PCP theorem where GAP-3SAT is the following problem: given a 3-SAT formula and a real number c, whether the formula is satisfiable or under every truth assignment at least c fraction of clauses remain unsatisfied. It is obvious that for small values of c this problem is NP-hard (since it is just SAT for small c), so the difficult question is the case of larger c values. Arora and Safra established a proof of PCP theorem which was long and algebraic. This paper presents a more combinatorial proof using reduction of a variant of GAP-3SAT for small values of c to the same variant of GAP-3SAT for larger values (actually constant values) of c. The variant of 3SAT is this: given a graph where each vertex of graph is a variable over a finite alphabet and each edge is a relation over that alphabet, and given a real value c, whether there is satisfying assignment to the vertices of the graph or always c fraction of edges remain unsatisfied.

The tool to prove this, is almost a standard approach: first we convert the graph to an expander using replacement and graph superimposition (union of a graph with an expander). Then using powering (an operation similar to zigzag product) we increase the "expansion" in the graph and it turns out that this increases the fraction of unsatisfied edges. In the last step using a technical method we decrease the size of the alphabet of the graph (which the powering operation increases that by an exponential factor). All these operations can be done in polytime and as a result the farction of unsatisfied edges double. If we repeat these steps for a logarithmic number of times, the fraction of unsatisfied edges becomes as large as a constant, which is the desired property.

David's Lectures

2005-12-08T22:26:00.000-08:00

Sorry, I forgot to post the url of the lecture notes for David's lectures. Meanwhile, I made a few changes. I could not write it up in html so prepared a pdf file:

http://www.geocities.com/hemanta_maji/lecture.pdf

Recap: Are Bitvectors Optimal?

2005-12-08T21:44:00.000-08:00

In the paper "Are Bitvectors Optimal?" we aim to answer the static membership problem -- that is, given a Universe U = {1, 2, ..., m} and a set S of keys from U, we want to know whether an element u known to be in the universe is in S. This, of course, could be answered with a simple idea of lying out all elements and querying a large number of elements to find if u is among them; however, we aim to minimize storage space and use as few probes as possible. We look at two types of randomized schemes to implement this, each using only one bitprobe. One has one-sided error (where an answer of "Yes, u is in S" might be incorrect) and another has two-sided error (where either a "Yes" or a "No" answer might be incorrect).

We start by making a bipartite graph G=(U,V,E) where U is the Universe and V are locations in memory. For the two-sided error problem we seek a two-coloring of V such that ∀ u ∈ S, at least (1-ε)|Γ(u)| locations are colored 1, and ∀ u' ∉ S, at least (1-ε)|Γ(u)| locations are colored 0 (where 0 maps to an answer of "no" and 1 to "yes"). This is also referred to as being "(n,ε)-two-colorable." The general idea about how we go about this is to separate out those vertices which can be colored 0 and 1 and have no potential for error, and then show that the error on the remaining vertices is bounded by ε. In particular, we use specific properties of the graph as an expander, showing that V has the "(n,ε) Intersection Property," which in essense says that the number of sets of locations which would be "offending" a simple greedy 0/1 coloring is less than the original number of sets. Thus, we take this smaller set of offenders and inductively find a good (n,ε)-two-coloring for it, then adding back in the original non-offender sets which were already properly colored.

Recap: Extractors

2005-12-01T12:03:00.000-08:00

For randomization it is common practice to assume some uniformally random source. However, such an assumption is unrealistic as most sources found in nature are biased. We therefore wish to utilize these biased sources of randomness to produce a perfectly random source. For some cases, this can be accomplished deterministically, however for many sources this is not the case. An example of which are Santha-Vazirani sources (δ-SV sources defined in the post of 10/22/05).
By construction of a δ-SV-source for any deterministic extractor of even a single bit such that the extractor using the source is as biased as the source itself in Proposition 1 we showed this.

A (k, ε)-extractor is then a function which takes some purely random seed of length d and any k-source X on {0,1}ⁿ and outputs some m length bitstring which is ε-close to unifom.
The proof of the existence of such extractors comes from the application of the probabilistic method considering a random choice of deterministic extractors (zero length seeds).
Constructive proofs such as the Leftover Hash Lemma guarantee extractors with specific bounds (A table of some of these bounds is located in the post of 10/22/05).

Extractors and expanders are interrelated as any extractor Ext: {0,1}ⁿ × {0,1}^d → {0,1}^m can be viewed as a bipartite multigraph G = { [N], [M], E } where an edge exists between v ∈ [N] and u ∈ [M] if and only if for some random seed the extractor on u outputs v.
On expection of the resulting graph the extraction property is equivalent to the expander mixing lemma thus the graph is an expander.
Similarly an expander can be used to create an extractor by making the expander into a bipartite graph in the usual way.

In the end we examined extractors over block sources. A block source is a generalization of a δ-SV-source where single bits are replaced with constant sized blocks of bits. Such sources can be used by extractors via the repeated application of an extractor on the individual blocks of the source. In doing so, the initial seed is applied only to the first iteration of the extractor generating some random bitstring r_iz_i. On the next iteration i - 1 the r_i bits resulting from the previous extraction are used as the seed. The resulting output is then r₁z₁z₂...z_i (note that the first iteration is i and each subsequent iteration has index i - 1). The proof of these bits' randomness is found by induction.

The PCP Theorem by Gap Amplification

2005-11-26T16:56:00.000-08:00

I have temporarily put my post here: http://www.cs.uiuc.edu/homes/zamani/mypost.xml

Seems I have to change something(s) in blog template to incorporate this soundly.

Are Bitvectors Optimal?

2005-11-21T18:34:00.000-08:00

Static Membership problem

Given
Universe U = [m]
Set S containing keys of U

Query
For some u, is u in S?

Main goal
Use few probes
Small storage space

Errors in Responding to Query

One-sided
if u is in S, correct ("yes")
if u is not in S, sometimes correct ("no"), sometimes incorrect ("yes")

Two-sided
if us is in S, sometimes correct ("yes"), sometimes incorrect ("no")
if us is not in S, sometimes correct ("no"), sometimes incorrect ("yes")

Space requirements

Error	Probes	Space (upper)	Space (lower)
2-sided	1	O(n/ε² log m)	Ω (n/(ε log(1/ε)) log m)
1-sided	1	O((n/ε)² log m)	Ω(n²/(ε² log n/ε)log m)

One-sided Error (minor result)
S is a subset of U.

Let G = (U,V) be a bipartite graph where U is the universe and
V is locations in memory.

For each u in S, color each of u's neighbors 1.

Note that if u is NOT in S, there may nevertheless
exist an edge from u to one of its neighbors.

Thus the one-sided error.

Query

Suppose we are given the query "is u in S?" for some u in U.

Then we probe a random neighbor of u. If this neighbor is 1, then
we return true, else false.

Result

We aim to exhibit a construction of G such that for all u' not in S,
fewer than ε |Γ(u')| neighboring locations are 1.

This guarantees that when probing u', the probability of an incorrect
response is less than ε |Γ(u')|.

We assume that |S| ≤ n.

Our construction is an (m,l,a)-design .

A family F is an (m,l,a)-design if F has m sets each of size l,
and any two sets in F have at most a elements in common.

A Theorem from an earlier work shows that an (m,l,a)-design can be guaranteed
when m, s, a and l are related in a certain way.

We use an (m,l,a)-design with a = log m, l = (n log m)/ε.

Correctness

If u is in S, then all of Γ are 1, thus we correctly return "yes".
If u is NOT in S, then we have that |U ∩ Γ(u)| ≤ na. Thus
we have that the probability of erroneously getting a 1 is bounded by
na/|Γ(u)| = na/l ≤ ε.

Two-sided Error (main result)

Consider bipartite graph (U, V, E) where U=[m] and V=[s].

We store the set S, where |S| ≤ n.

We use the same query scheme as before: for the query "is u in S?" we return
true if a random vertex of Γ(u) is colored 1, false otherwise.

We want the error probability to be at most ε. We seek a two-coloring
&X:V →{0,1} such that:

∀ u ∈ S, at least (1-ε)|Γ(u)| locations are colored 1
∀ u' ∉ S, at least (1-ε)|Γ(u)| locations are colored 0

Definition: Let C₁, C₀ be subsets of 2^V. We say that
(C₁,C₀) is ε-2-colorable if there exists
X:V →{0,1} such that:

For all T in C₀	\|X^-1(1) ∩ T\| ≤ ε \|T\|
For all T in C₁	\|X^-1(0) ∩ T\| ≤ ε \|T\|

Further, we say that C is (n,ε)-2-colorable if for all subsets

(C₁,C₀) of C
such that |C₁| ≤ n and C₀=C-C₁, we have that

(C₁,C₀) is ε-2-colorable.

Our Goal

We wish to find a bipartite graph G=(U,V,E) such that U=[m], V=[s]
and {Γ(u)}_{u in U} is (n,ε)-2-colorable. This will give
ensure that our query procedure is never wrong more than ε fraction of the
time.

We show that such a graph exists, with |V|=O(n/ε² log m):

G = (U, V, E) is an (m, s, n, d, ε)-expander

{Γ(u)}_{u in U} has the (n, ε)-intersection property

{Γ(u)}_{u in U} is (n, ε)-2-colorable

(n, m, s, 1)-randomized scheme with error ε

G = (U, V, E) is an (m, s, n, d ε)-expander

G=(U,V,E) is an ε-expander => {Γ(u)}_{u in U} has (n,ε)
intersection property

This is proved via induction on |C₁| and |C₀|.

C has (n,ε)-intersection property => C is (n,ε)-two-colorable

Definition: G=(U,V,E) is an (ms,n,d,ε)-expander if U=[m], V=[s],
each vertex in U has degree d and for all subsets S of size less than or equal
to 2n we have that |Γ(s)| ≥ (1-ε/2) |S|d .

We prove the contrapositive. We assume that we do not have the (n,ε)-intersection
property. Then we show that:

|Γ(S)| < (1-ε/2)|S|d, a violation of the definition of an expander.

Undirected ST-connectivity in logspace

2005-11-07T13:35:00.000-08:00

The undirected ST connectivity (USTC) problem is: given an undirected graph G=(V,E) and two vertices s,t, decide whether or not s and t are in the same connected component of G. The proof that USTC is in L (deterministic logspace) makes good use of expanders.

We first reviewed what results were known about USTC and the logspace complexity classes. It was known that USTC is complete for SL, languages accepted by nondeterministic logspace machines whose transition functions are "symmetric" in a certain sense. The directed version of ST connectivity is complete for NL, while connectivity in undirected forests is complete for L.

L ⊆ SL ⊆ NL ⊆ DSPACE(log² n)

The last inclusion is from Savitch's theorem. Showing that USTC ∈ L yields L = SL.

The algorithm for USTC proceeds roughly as follows. Given input ⟨G,s,t⟩:

Convert G to a regular graph G_reg in a way that preserves connected components.
Amplify G_reg's expansion properties by powering operations and taking zig-zag products appropriately (again preserving connected components). Call the result G_L.
Since G_L is a good expander, it has logarithmic diameter. Thus we can simply perform a bounded-depth DFS on this graph from s' to determine reachibility of t'.

Of course, these intermediate graphs are not computed in memory. To do the last step, we only need to be able to compute G_L's rotation map in logspace. This is possible, with recursive calls to the intermediate graphs, and finally using the original G's adjacency relation as the base case.

Converting G to G_reg: Assuming V(G) = {1, ..., n}, we perform a replacement product on G, where each vertex u is replaced with an n-cycle whose vertices are { ⟨u,v⟩ | v ∈ V(G) }. If u and v were connected in G, we connect new vertices ⟨u,v⟩ and ⟨v,u⟩. We add self-loops everywhere else so that the degree becomes D¹⁶, where D is a constant we'll define later.

We label edges in the replacement cycle as 1 & 2, and possible edges between cycles as 3. In terms of the rotation map, this looks like:

R( ⟨u,i⟩, 1 ) = ( ⟨u, (i-1)%n⟩, 2 )
R( ⟨u,i⟩, 2 ) = ( ⟨u, (i+1)%n⟩, 1 )
R( ⟨u,v⟩, 3 ) = ( ⟨v,u⟩, 3 ), if u and v are connected in G, and ( ⟨u,v⟩, 3 ) otherwise
R( ⟨u,v⟩, i ) = ( ⟨u,v⟩, i ), for i > 3

It is easy to see that this construction preserves connected components, and that this rotation map can be computed in constant space. The size of the graph increases quadratically, so logarithmic quantities in the size of G_reg are also logarithmic in G.

Converting G_reg to an expander: This operation uses powering and zig-zag operations, so let's review how these operations affect expander properties. We say a graph is (N, D, λ) if it has N vertices, is D-regular, and λ is its 2nd largest normalized eigenvalue magnitude.

Powering a graph (G → G^k) changes it from a (N, D, &lambda) graph to a (N, D^k, λ^k) graph.
The zig-zag product G z H, where G is a (N, D¹⁶, λ) graph, and H is a (D¹⁶, D², α) graph, results in a graph which is (ND¹⁶, D, f(λ,α)).
Combining these two operations, if we take G and H as above, the graph (G z H)⁸ is (ND¹⁶, D¹⁶, f⁸(λ,α)).

Note especially that the graph (G z H)⁸ has suitable degree for us to zig-zag it again with H.

The reason for the appearance of D¹⁶ is that it is possible to show with a probabilistic argument that there exists some constant D and a graph H which is (D¹⁶, D, 1/2). This will be the value of D we'll use, and the graph H will be a constant that is hard-coded into the algorithm.

Now, we define a sequence of graphs as follows:

G₀ = G_reg
G_i+1 = (G_i z H)⁸

It follows that G_i has ND^{16 i} vertices and degree D¹⁶. Let us now see how these operations affect the λ parameter.

Let &lambda_i be the λ parameter of G_i. Using a bound on the f() function from the zig-zag product, we inductively proved a lemma that &lambda_i < max{ (λ₀)^2ⁱ, 1/2 }. In other words, the eigenvalues of the G_i sequence decrease geometrically until they reach 1/2, after which they stay below 1/2. (Actually, the argument is more subtle. We actually apply this bound to each of G_i's connected components separately, since it is only valid for connected graphs).

We also proved a lemma that for any D-regular non-bipartite graph on N vertices, its 2nd largest normalized eigenvalue magnitude is at most 1 - 1/DN². That is, every regular graph has a nonnegligable spectral gap. Our graph G₀ is non-bipartite (it has self-loops at every vertex). So combining these two observations about the eigenvalues, we see that for L = O(log N), the graph G_L has λ_L < 1/2. Its size is also polynomial in N. The graph G_L will be our final expander.

Computing G_L's rotation map in logspace:

Vertices in G_i correspond to a vertex in G_i-1 along with an edge number (which together comprise a vertex in the replacement product), and edges in G_i consist of 16 "zig-zag" edge labels (due to powering the graph to the 8th power). Once the description of such a vertex ⟨v,a⟩ and edge label ⟨i₁,...,i₁₆⟩ are written down in memory, we can compute the rotation map with very little memory overhead:

To compute R_{G_i}(⟨v,a⟩, ⟨i₁,...,i₁₆⟩):
- For j = 1 to 16 do:
- ⟨a,i_j⟩ = R_H(a,i_j)
- If i is odd, then do ⟨ v,a⟩ = R_{G_i-1}(v,a)

The final result is is ⟨v,a⟩, ⟨i₁₆,...,i₁⟩. Note that we use a recursive call to compute the rotation map of G_i-1, which is allowed to rewrite the memory of its argument in the same manner. Analyzing this algorithm, we see that at each level of recursion, we only need to keep track of loop variable j and our position i in the recursion, taking O(log N) space.

Putting it together:

Finally, to determine connectivity between s and t, we perform a DFS on G_L starting at a representative for s and looking for a representative of t. Since it is an expander with a constant spectral gap, it has logarithmic diameter, and we can bound our DFS to O(log N) steps without loss of generality.

To keep track of our position in the DFS, we only need to keep track of the current vertex's description, and the last edge label we traversed, which takes only O(log N) bits. The symmetric nature of the rotation map allows us to "back up" in the DFS tree. When we back up, we will have the label of the edge that was just taken from the vertex, which we can increment to recurse again (or back up again if it is this vertex's last unvisited edge).

Recap: Amplifying one-way functions

2005-10-31T13:34:00.000-08:00

One-way functions are functions that are computable in polynomial time but not invertible on average in randomize polynomial time. We formalized this by defining α-one-way permutations (α-OWP) where α is essentially the fraction of inputs on which the function is hard to invert.

To use an OWP f to construct an even harder-to-invert OWP F, it is essential that the construction apply f to many different inputs. Instead of naïvely applying f to some number of independent inputs, our construction applies f to inputs along a random expander walk, which turn out to be "independent enough."

To compute F on input 〈x,σ₁,...,σ_k〉:

For i ← 1 to k:
- x ← f(x)
- x ← R_G(x,σ_i), the σ_i-th neighbor of x in an appropriate expander graph G
return 〈σ₁,...,σ_k,x〉

The input to F is the description of a walk on G, and as such the length of inputs to the OWPs increases by an additive factor of O(k) (taking the degree of G to be constant), instead of by a multiplicative polynomial factor if we were using independent inputs to f. This is a significant increase in efficiency.

The construction of F from f can be viewed as a walk on the graph whose edges are { ⟨f(u),v⟩ | ⟨u,v⟩ ∈ E(G) }, which is also an expander with the same properties as G since we take f to be a permutation. Using a random walk lemma (very similar in flavor to previous random walk lemmas) and a simulation argument, we can show that if f is a (1-α)-OWP, then F is a (1-α^k/2)-OWP.

Starting with any 1/poly-OWP f, we can apply this construction several times with the appropriate parameters to get a (1-1/q(n))-OWP, for any polynomial q(n), and the overall increase in input length is only an additive factor of O(log n). This is significantly better than previously-known constructions which increased the input length by a multiplicative factor of at least n².

Extractors (Phillip Mienk, lecturer)

2005-10-22T14:16:00.000-07:00

Motivation: For most of what we've been talking about in the past, we've been assuming we've had perfectly random sources, but these creatures simply can't always be found in "nature." The question then arises -- can we take a source which is biased and bring it as close as possible to purely random?

We take to start a result from vonNeumann: For any

X

₁, X₂,...,X_n∈{0,1} with Pr[X_i = 1] = δ_i, where 0<δ≤δ_i≤1-δ, then for l such bits, we can bound the parity to be exponentially close to 1/2. That is, |Pr[ XOR_i=1...l X_i = 1] - ¹/₂| = 2 ^-Ω(l).δ-SV-sources (Santha-Vazirani): ∀i ∀x₁, ..., x_i-1 such that δ≤Pr[X_i=1 | X₁=x₁, ..., X_i-1=x_i-1] ≤ 1-δProposition 1: ∀δ for all deterministic extractors f(x)=b (functions which output one bit), ∃ an SV-source X such that Pr[b = 1] is as biased as the SV-source.Proof: Consider X_i, ..., X_n ∈ D = {0,1}ⁿ. Let f(x)=b. Note that |D|=2ⁿ. Divide the domain, D, into two pieces, D₀ where the extractor outputs 0, and D₁ where the extractor outputs 1. D₀={x: f(x)=0}, D₁={x: f(x)=1}. We want to show there is an SV-source such that f is δ-biased; if the uniform distribution doesn't work, then the difference between the sizes of our two domains must be | |D₀| - |D₁| | ≤ 2ⁿδ. WLOG, we say |D₀| ≥ |D₁|. Then there are |D₀|≤ (^2ⁿ/₂) + (^2ⁿδ/₂) = ^{(1 + δ)}/₂ ·2ⁿ. Thus, |D₁|≥ ^{(1 - δ)}/₂ ·2ⁿ. Let X be an SV-source such that ^{(1 + δ)}/₂ on D₀ and ^{(1 - δ)}/₂ on D₁. If x ∈ D₀, Pr[x] = ^{(1 + δ)}/₂ · ¹/_|D₀|. If x ∈ D₁, Pr[x] = ^{(1 - δ)}/₂ · ¹/_|D₁|. Now let's say we have strings a=y0 and b=y1, where |y|=n-1 (we would like to show that |Pr[a|y]-Pr[b|y]|<δ). It is enough to bound the ratio of ^Pr[a|y]/_Pr[b|y] = ^Pr[a]/_Pr[b]. If a,b∈D₀ or a,b∈D₁, this ratio is obviously exactly 1; thus we assume WLOG that a∈D₀ and b∈D₁. Then, ^Pr[a]/_Pr[b] = (^{(1 + δ)}/₂ · ¹/_|D₀|)/(^{(1 - δ)}/₂ · ¹/_|D₁|) = ^{(1 + δ)}/_{(1 - δ)} · ^|D₁|/_|D₀| ≤^{(1 + δ)}/_{(1 - δ)}. With some more elementary algebra (which would just look overly intimidating with the terrible typsetting on this blog), we can also get a lower bound of 1. Thus, for all f we have constructed a δ-SV-source, namely ^(1+δ)/₂ on D₀, ^(1-δ)/₂ on D₁.More motivation: Why are we doing this? We want to run randomized algorithms given an extractor and input. If it doesn't yield significantly random output, then we can allow a purely random seed into the extractor, and we hope that this will make the output more uniformly random. From an algorithm A(w,r) we can make a new algorithm A'(w,X) with the same input and k-source X and generates all possible bits it can from a given seed, d. For small d, we can iterate over all seeds until we find the one that gives optimal output, and thus we'd like to prove there exist extractors with small seeds.Definition: Ext: {0,1}ⁿ × {0,1}^d → {0,1}^m is a (k,ε)-extractor if for any k-source X on {0,1}ⁿ then Ext(X,U_d) is ε-close to U_m.Definition: The statistical difference, Δ, is half the L₁-difference. That is, Δ(x,y) = max_T⊆U |Pr[x∈T]-Pr[y∈T]|Definition: Supp(X)={x : x∈X, Pr[x]>0}Proposition 2: For any n and for any k≤n, and a flat (uniform over {0,1}^k) k-source X, ∃ Ext: {0,1}ⁿ → {0,1}^m with m=k-2log(¹/_ε)-O(1) such that Ext(X) is ε-close to U_m.Proof: Consider a random deterministic Extractor. We want ∀T ⊆ [2^m] |Pr[Ext(X)∈T] - Pr[U_m∈T]|≤ε. This would imply that ^{|{x∈supp(X) : Ext(x)∈T}|}/_2^k differs from density μ(T) by less than ε. (The rest of the proof is left to the reader, as class ended and notes were left incomplete.)Deterministic Extractors: Fix Y a flat l-source on {0,1}^t. As there are L=2^l desired elements from T=2^t possible, we have (T choose L) candidates for Y. By Stirling's approximation, this is ≈(^Te/_L)^L. Consider a random extractor Ext: {0,1}^t → {0,1}^m. Pr[Ext not an extractor on Y] ≤ 2^Ω(Lε²). This implies that Pr[Ext not an extractor for some Y] ≤ (T choose L) · 2^-Ω(Lε²) ≤ (^Te/_L)^L · 2^-Ω(Lε²) > 1. Thus the deterministic extractor fails.Randomized Extractors: Consider Y=(X,U_d), where X is a flat k-source with t=n+d. (Notation: T=2^t, N=2ⁿ, D=2^d, K=2^k). Then T=ND, L=KD, and there are (N choose K) candidates for Y. Pr[Ext fails for some Y] ≤ (N choose K) · 2^-Ω(KDε²) ≤ (^Ne/_K)^K · 2^-Ω(KDε²), which is less than 1 if d=log(n-k) + 2log(¹/_ε)+O(1). Since this probability is less than one, there is a high probability we have an extractor for all Y, and thus we can have randomized algorithms.Recall that we're looking to find a small seed, d, while giving good output, m. What do we know?

	d	m
Necessary for BPP simulation	O(log n)	k^Ω(1)
Pairwise Independant Hashing	O(n)	k+d-O(1)
Spectral Expanders	O(n-k)	n
Lu, Reingold, Vadhan, Widgerson	O(log n)	(1-γ)k, ∀γ>0
Zig-Zag Product	O(log²n)	k+d-O(1)

Definition: A family of functions H={h_i : [N] → [M]} is pairwise independent if (1) ∀x∈[N], h(x) is uniformally distributed in [M] (2) ∀x,y∈[N], x≠y, h(x) and h(y) are independent.Leftover Hash Lemma: If H={h : {0,1}ⁿ → [0,1}^l} is a pairwise independent family where l=k-2log(¹/_ε)-O(1), then Ext(x,h) = (h, h(x)) is a (k,ε)-extractor. (Not enough time for the Proof in class)Extractors and Expanders: We can interpret Ext: {0,1}ⁿ × {0,1}^d → {0,1}^m as a bipartite multigraph G=([N],[M],E) where (u,v)∈E iff ∃r∈U_d such that Ext(u,r)=v. Consider the extraction property that Ext is a (k,ε)-extractor iff ∀S⊆[N], |S|=K, Δ(Ext(U_s,U_d),U_m) = max_T⊆[M] |Pr[Ext(U_s,U_d)∈T] - Pr[U_m∈T]| ≤ ε Therefore, for any T⊆[M], this implies that |(^e(S,T)/_|S|·D) - (^|T|/_M)|≤ε. This looks familiar; recall the...Expander Mixing Lemma: For S,T⊆G and λ the second largest eigenvalue of the adjacency matrix A, |(^E(S,T)/_|S|·|T|) - (^D/_N)| ≤ λ√(|S|·|T|). Note that we can make G bipartite by making a copy of G, selecting S in G₁, T in G₂, and if uv∈G, ∃uv∈G₁G₂ such that u∈G₁ and v∈G₂. Through some manipulation of the two similar equations, one can see that if λ is "small enough," an expander yields an extractor (and vice versa).Definition: X is a (k,l) block source if X=B₁...B_t where ∀i∈[t], |B_i|=l and ∀b₁, ..., b_i-1∈{0,1}^l, B_i|_{B₁=b₁, ..., B_i-1=b_i-1} is a k-source. Alternatively, X is a (k,l) block source if it can be partitioned into l blocks of equal size such taht conditional distribution of each block given previous history is a k-source.Theorem: Given explicit construction for (k,ε)-extractor Ext: {0,1}^l × {0,1}^d → {0,1}^d+m, then ∀t≥1 ∃ Ext': {0,1}^tl × {0,1}^d → {0,1}^d+tm such that Ext'(X,U_d is tε-close to U_d+tm for all (k,l) block sources X with t blocks. Formally, consider Ext'. For x∈{0,1}^tl, x=b₁...b_t for |b_i|=l. For each b_i, Ext yields r_iz_i with |r_i|=d. Then Ext(b_i,r_i+1), where r_i+1 is the initial seed, d. Thus, &delta(Ext'(X,U_d), U_d+tm)≤tεProof: X=B₁...B_t. Let R₁, ..., R_t+1 and Z₁, ..., Z_t be random variables representing the output of Ext'(X,U_d) and internal output. Let M₁, ..., M_t be samples of U_m. Define ∀i∈[t+1]: D_i = (B₁, ..., B_i-1, R_i, Z_i, ..., Z_t) and E_i = (B₁, ..., B_i-1, U_d, M_i, ..., M_t). We want to show that Δ(D_i,E_i)≤(t+1-i)ε, and we shall proceed by induction. Base case: i=t+1. Since R_t+1 is a seed, it is uniform in U_d. Inductive hypothesis: Δ(D_i+1,E_i+1) ≤ ((t+1) - (i+1))ε ≤ (t-i)ε. Inductive step: &Delta (D_i+1,E_i+1) = Δ( (B₁, ..., B_i, R_i+1, Z_i+1, ..., Z_t), (B₁, ..., B_i, U_d, M_i+1, ..., M_t) ) = Δ( (B₁, ..., B_i, Ext(B_i, R_i+1), Z_i+1, ..., Z_t), (B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t) ). But Ext(B_i, R_i+1) = R_iZ_i. Thus, the same quantity = Δ(D_i, (B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t)). We know that B_i is a k-source conditioned on B₁, ..., B_i-1, that Ext is a (k,ε)-extractor, and that M_i, ..., M_t are independent. Thus, our quantity = Δ((B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t), (B_i, ..., B_i-1, U_d+m, M_i+1, ..., M_t))≤ε Consider the triangle inequality: &Delta(D_i, E_i)≤ Δ(D_i, (B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t)) + Δ((B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t), E_i) ≤ (t-i)ε + ε ≤ (t+1-i)εSince this has worked for any block source, we can then generate similarly for an SV-source.

Recap: Randomness conductors and lossless expanders

2005-10-17T13:26:00.000-07:00

In the next lectures (9/28-10/5), we showed how to construct explicit constant-degree lossless bipartite expanders (Capalbo, Reingold, Vadhan and Wigderson, 2002). The main idea is to use a variation of the zig-zag product with added "buffers" to catch randomness that would otherwise be wasted. It is known that some Ramanujan graphs are not lossless expanders so the paper needs to use something beyond standard eigenvalue methods. Instead it introduces conductors, functions to manipulate random distributions, and uses min-entropy to measure their performance.

The modified zig-zag product takes three conductors arranged as shown below.

The largest component (C₁ in the figure) is a permutation on (node,walk) pairs in an expander graph (which takes a pair (node₀,walk) to (node',walk') where node' is the endpoint of the walk starting from node₀, and walk' is walk "viewed backwards"). The other two components have constant size and so can be found via exhaustive search.

The output of the first two conductors preserve all the entropy present in their inputs, and C₃ is a lossless conductor applied to the "buffers" of these conductors.

(Instead, if C₃ is an extractor, the resulting conductor is also an extractor; note that since the output of the first component itself is almost as long as the input, this is true only for high min-entropy inputs (i.e. inputs with at most a constant number of bits of entropy deficiency).)

Recap: The Zig-Zag Product

2005-10-16T22:28:00.000-07:00

Given a large graph and a small(er) graph, the zig-zag product of the two graph is a larger graph with degree equal to the size of the small graph squared, which has 2nd largest eigenvalue bounded by the sum of the 2nd largest eigenvalues of the original graphs.

To see what the zig-zag is, we use an intermediate graph, the replacement graph. Note that the degree of G₁ is equal to the number of vertices in G₂. Then the replacement graph G₁ r G₂ consists of replacing each vertex of G₁ with a copy of G₂, so that each vertex in the new graph has all its edges in the local copy of G₂ as well as 1 edge from G₁ which leads to a different copy of G₂.

Then the zig-zag product, G₁ z G₂, has an edge for every path of length 3 in the replacement graph which consists of an edge in a local copy of G₂ followed by an edge from G₁ followed by an edge in the new local copy of G₂. So the degree of a vertex in the zig-zag is the degree of G₂ squared.

Intuitively, the zig-zag works well because if the starting distribution is far from uniform, then the first step in the path of length 3 increases entropy by simply being a step in an expander. If the starting distribution is close to uniform on the component corresponding to the local copies of G₂, then the middle edge in the path of length 3 steals some of the entropy for the first component corresponding to the larger graph G₁, and then the G₂ componenet will be further from uniform so that the third step will increase overall entropy.

The zig-zag product can be iterated to yield an infinite family of expanders where degree remains constant. They are not Ramanujan, since the best possible eigenvalue bound we can get is O(1/D^1/4) for a D-regular expander.

Recap: Edge and Vertex Expansion

2005-10-15T17:26:00.000-07:00

In the edge expansion lecture, we saw a proof that for a d-regular graph G,

(d - λ₁)/2 ≤ h_G ≤ sqrt(2d(d - λ₁))
(See Manoj's post below for definitions.) As a consequence, we see that our two definitions of an expander family are equivalent.

In the vertex expansion lecture, we saw that vertex expansion is also related to the spectral gap. Analogously to edge expansion, define the vertex expansion h'_G as

h'_G = min_|S|≤n/2 |N(S)|/|S|
where the minimization is over all subsets S of at most half the vertices of G, and where N(S) = { v : there exists u in S with uv an edge }.

Let λ^* be max {| λ_i|}. For any d-regular graph G,

2/((λ^*/d)² + 1) ≤ h'_G ≤ sqrt(2d(d - λ₁)) + 1
Note that λ^* appears in the lower bound and λ₁ appears in the upper bound. The upper bound follows from the relatively simple observation that h'_G ≤ h_G + 1.

Solving the second inequality for λ₁, we obtain an upper bound

λ₁ ≤ d - (h'_G - 1)²/2d
Finally, we note that, when d is large, better bounds on λ₁ are known. A result of Noga Alon (1986) shows that

λ₁ ≤ d - (h'_G - 1)²/(4 + 2(h'_G - 1)²)

Summary of first few lectures

2005-10-14T07:00:00.000-07:00

We defined an expander family as a familty of undirected, regular graphs on n vertices (for increasing n) such that the degree is constant and

the edge expansion (h_G=min_|S|≤1/2 |E(S,S')|/|S|) is at least a constant, OR
the spectral gap (d-λ₁) is at least a constant.

(The equivalence follows from (d-λ₁)/2 ≤ h_G ≤ sqrt[2d(d-λ₁)], proven later.)

A slightly stronger definition of spectral expansion requires d-λ to be at least a constant, where λ=max(|λ₁|,|λ_n-1|). Then we have the following for an expander G (writing α for λ/d).

Optimal Expanders: If we allowed "fractional edges," a clique (with self-loops) with all edge weights d/n would be the best degree d expander (with λ=0). However, with "integral edges," λ ≥ 2 sqrt[d-1] - o(1). So called Ramanujan Graphs have λ = 2 sqrt[d-1]. So one can think of α being O(1/sqrt d).

Expander Mixing Lemma: For any cut (S,T) in G, number of edges across the cut is in the range (d/n)|S| |T| ± dα sqrt[|S| |T|]. (Note that the smaller the α the closer this is to the value for the "d/n-clique.")

An application of this lemma is in a simple "deterministic amplification" of BPP algorithms: the algorithm is run not just on one random-tape, but on all its d "neighbors" too -- neighbors in an arbitrary expander with the space of all random-tapes as the vertex set -- driving the error probability down to O(α²), starting from say 1/4.

Rapid Mixing: Starting from a distribution p on the n vertices, a t-step random walk on G results in a new distribution M^tp exponentially close to the uniform distribution u. More precisely, the L₂-norm of the difference M^tp - u is at most α^t (and hence the L₁-norm, which measures twice the statistical difference, is at most (sqrt n)α^t).

Sampling by Random Walks: Probability that a t-step random walk is confined to a set B of size βn is between (β-2α)^t and (β+α)^t. (Note that the smaller the α the closer this is to β^t corresponding to the random walk on the clique.)

The upperbound lets one amplify a BPP algorithm to reduce the error probability exponentially in t using only t log d extra random bits than the original BPP algorithm (if its error probability is a sufficiently small constant to begin with).

The two bounds together can be used to deterministically sample a graph such that the relative size of the max-clique is preserved. This lets one reduce the approximation factor of an algorithm for approximating the size of a largest clique, by first using a graph exponentiation which preserves the relative log-size of the max-clique and then sampling it down as above to a polynomial sized graph in which the original approximation algorthm is then run. (Such an improvement in approximation factor can be used to amplify hardness of approximation results.)

Amplifying the hardness of one-way functions

2005-10-13T08:32:00.000-07:00

We began by defining a negligible function. A function β(n) is said to be negligible if ∀ c > 0 β(n) < 1/(n^c) for sufficiently large n.

We then defined a one-way permutation: a polynomial-time computable permutation f is α(n)-one way (denoted by α-OWP) if for any probabilistic polynomial-time algorithm A:
Pr[A(f(x)) = x] ≤ 1 - α(n) + β(n)
where the probability is over all strings x of length n and the coin-flips used by the algorithm, and β(n) is some negligible function. Intuitively, f is α-OWP if the fraction of 'hard' inputs is close to α.

Finally, for sets X and Y where X ⊆ Y, we say that X has density μ if |X| = μ|Y|

It is not obvious that one-way permutations exist, but our first theorem (due to Yao) shows that we can construct strong one-way permutations from weak ones. Given f, a (1/p(n))-OWP on n-bit strings for some polynomial p(n), we define:
F(x₁, x₂, ..., x_t) = f(x₁)f(x₂)...f(x_t)
where |x_i| = n, and t = n⋅p(n). That is, F is a function on n²⋅p(n)-bit strings formed by applying f to each part of size n, and concatenating the results. To invert F, we must invert f on each part; the large number of parts means that we expect several of them to be hard for f. It can be shown that in fact, F is hard to invert on all but a negligible fraction of the range.

The chief problem with this method is that the input length blows up by a large polynomial factor. If f used n bits, F uses n²p(n) bits. Therefore, the hardness of inverting F on large inputs (say of length m) relates to the hardness of inverting f on much smaller inputs (those of length m^ε, where ε is a constant ≤ 1/2).

A better idea to amplify hardness is to run f on many inputs, but instead of selecting the inputs independently at random, construct an expander graph where each node corresponds to an n-bit input string. Now, select the first node randomly, and then perform a random walk in the graph. Run f on every node v in the walk; the nodes are 'independent enough' that with good probability, we will find some node v such that f(v) is hard to invert.

Lemma 1: Let α(n) be at least 1/p(n) for some polynomial p. The following are equivalent:
(a) f is α-OWP
(b) For any polynomial-time randomized algorithm A, ∃ H ⊆ Σⁿ of density ≥ α such that
Pr[A(f(x)) = x | x ∈ H] is negligible.

Intuitively, H is the 'hard' set for algorithm A; that is, the lemma says that if f is an α-OWP, there is some set H (of density at least α) of inputs that is hard to invert, and the converse. It follows almost immediately from the definition of an α-OWP that (b) implies (a). The other direction is also not difficult to prove; if there is an algorithm A with a hard set of density < α, repeated applications of this algorithm allow us to invert f with probability > 1 - α, contradicting the fact that f is α-OWP.

Lemma 2: Let G be an (N, d, λ) expander. (G has N vertices, is d-regular, and λ is the normalized second-largest eigenvalue.) For any subset S of the vertices, with density μ, the probability that a random walk of length k is contained entirely within S is ≤ μ^k/2.

The proof of this lemma uses a technique we saw earlier. Let P be the projection vector with 1s in positions corresponding to elements of S, and A the normalized adjacency matrix of G. If u is the uniform unit vector, the desired probability is ||(PA)^k u|| ₁. (To see this, observe that we begin with a vertex picked uniformly at random; the probability that we are in S after a single step is given by the L₁-norm of PA(u) because Au gives us the probability distribution over vertices after a single step, and we sum over all the probabilities in S.)

The algebra required to bound ||(PA)^k u|| is a little too tedious for a blog post (with applications of the law of cosines, the Cauchy-Schwartz inequality, etc.), but it is fairly straightforward.

Theorem 1: (Main) If f is (1-α)-OWP on n-bit input strings (where α ≥ 1/2), we can construct F_k, which is (1 - α^k/2)-OWP on input strings of length n + k log d, where k is a polynomial and d a constant.

Proof: Let {G_n} be an expander family on 2ⁿ vertices, with degree d, and λ ≤ 1/2. We label edges such that R_{G_n}(v, i) = (u,i) for all v and i. That is, we label edges such that if the edge between v and u is the i^th edge of v, it is also the i^th edge of u; an alternate way to think about this is that the edge labels give us d disjoint perfect matchings in the graph. We now define F_k(x, σ₁, σ₂, ..., σ_k) (where |x| = n, and each σ_i ∈ {1...d}) as the output of the function:
for i ← 1 to k
x ← f(x)
x ← R_{G_n}(x, σ_i)
return (σ₁, σ₂, ..., σ_k, x)

That is, we apply f on x, take a step in the graph, and repeat this process k times. Another interpretation is that we take a k-step walk based on the σ_is in the graph G'_n, which has the same vertex set as G_n, but has an edge between u and v ⇔ G_n has an edge between f(u) and v. Since f is a permutation, G'_n is also an expander with the same properties as G_n.

To see that the function F_k is a permutation, it is sufficient to see that it is injective. Suppose two different inputs produced the same output; this implies that the walks ended at the same vertex and that the sequence of &sigma_is is identical. But two such walks that begin at distinct vertices can never converge, because f is one-to-one, and the &sigma_i^th edges from two different vertices cannot lead to the same vertex, because of the way edges are labelled.

We show that F_k is a (1-α^k/2)-OWP, by using any algorithm A that inverts F_k to construct an algorithm A' that inverts f; if the hard set for A has size < 1-α^k/2, the hard set for A' will have size < α. Given A, the algorithm A' works as follows to invert an input y:
Pick i from {1, 2, ..., k}
∀ 1 ≤ j ≤ k Pick σ_j uniformly at random from {1, 2, ..., d}
Set y' ← F_k-i-1(R_{G_n}(y, σ_i), σ_i+1, ..., σ_k
Use A to find (x', σ₁, σ₂,...,σ_k) ← F_k^-1(y', σ₁, σ₂,...,σ_k)
Return x ← F_i-1(x', σ₁, σ₂,...,σ_i-1)

Intuitively, to find the pre-image of y, A' picks i to be some position in a k-step walk. The algorithm follows the walk to the end, inverts it, and then follows the first part of the walk, stopping just before it reaches y. This vertex will be the predecessor of y in the walk. If A successfully inverts F_k, A' will invert f.

Since f is a (1-α)-OWP, A' must have a hard set of density ≥ 1-α. Let H be the set of vertices corresponding to the inputs in the hard set, and H* be the set of length k-walks in the graph that intersect H. From lemma 1, we know that H* has density at least (1-α^k/2). If we can show that H* is a hard set for A, it follows that F_k is a (1-α^k/2)-OWP.

If H* is not a hard set for A, then the algorithm succeeds with non-negligible probability (≥ 1/p(n)) on H*. For every invocation of A by A', with probability ≥ 1/k, the index i points to some vertex x ∈ H. Considering all paths in H*, the probability of A succeeding is ≥ 1/p(n). Therefore, the probability of A' succeeding on H is ≥ 1/(k ⋅p(n)), which is non-negligible; this implies that H is not hard for A'. But this is a contradiction, and so H* must be a hard set for A. This completes our proof of the main theorem.

Theorem 2: If f is a 1/p(n)-OWP for some polynomial p(n), then for any polynomial q(n), ∃ a (1- 1/q(n))-OWP with only an O(log n) (additive) increase in input length.

Proof: We use the construction of theorem 1 in two stages: First, starting with a (1 - (1-1/p(n)))-OWP, set k = O(1) and construct a (1 - (1-1/p(n))^k/2)-OWP by applying theorem 1; this only increases the input length by Θ(1) bits. Repeating this process O(log p(n)) = O(n) times, we can achieve a (1- 1/2)-OWP, with a total of O(log n) increase in input size. Now, set k = log q(n) = O(log n) and apply the construction to the (1- 1/2)-OWP; this gives us the desired (1-1/q(n))-OWP. The total increase in the iterations of stage 1 was O(log n), as it was in the single iteration of stage 2.

Introduction to Zig-Zag

2005-10-01T14:55:00.000-07:00

Starting September 21st, Erin introduced us to the Zig-Zag product as a means of expander construction.

In leading up to the construction, we first defined a rotation map of a graph G = (V,E) to be a function from pairs (v, i) to (w, j) where v,w ∈ V and the i-th incident edge to v leads to w, and it leads through the j-th incident edge to w. Further, we will use the notation that G is a (N, D, λ)-graph if G has N-vertices, is D-regular, and has second largest eigenvalue in absolute value, λ = max _{α ⊥ 1_n} | ⟨ α, M α ⟩ | / ⟨ α, α ⟩.

Next we explored the results of squaring and the tensor product of a graph. Namely, we considered G^t for G an (N,D, λ)-graph. Proposition 1 stated that G^t is an (N, D^t, λ^t)-graph. To see this, consider the normalized adjacenty matrix for M^t for G^t. Then M^tu = λ^tu from repeated iterations of Mu = λu.

We then defined the tensor product G of G₁ and G₂ where G₁ is N₁-vertex D₁-regular and G₂ is N₂-vertex D₂-regular to be a N₁ · N₂-vertex D₁ · D₂-regular graph such that the rotation map of the tensor product G is

R_G( (v,w), (i,j) ) = ( (v',w'), (i',j') ) where v ∈ G₁, w ∈ G₂, i ≤ D₁, j ≤ D₂ and R_G₁(v,i) = (v',i'), R_G₂(w,j) = (w',j')

This is a replacement of each vertex in G₁ with a copy G₂ and connecting all vertices based on the vertices they represent in G₁.

As the graph can be represented by the adjacency matrix, we consider the tensors effect on the two adjacency matricies A and B. If we let Au = λ₁u and Bv = λ₂v and let C be the tensor of A and B and let w be the tensor of u and v, then the product of Cw = λ₁λ₂w. We see this by considering the tensor of Au and Bv, extracting the appropriate position (i,j) in the resulting matrix.

Now, we consider the effect of the tensor. We considered Proposition 1 which states,

Let G₁ be a (N₁, D₁ λ₁) and G₂ be a (N₂, D₂, λ₂) graph. Then the tensor of the two is (N₁ · N₂, D₁ · D₂, max{ λ₁, λ₂ }).

To see this, consider the eigenvalues of the normalized adjacency matrix of the tensor. These eigenvalues depend on the normalized adjancency matricies of the original graphs G₁ and G₂. As the result of the tensoring of these normalized adjacency matricies results in a largest eigenvalue of 1, the second largest value is either λ₁ or λ₂.

From here we defined the Zig-Zag product. Consider G₁ a D₁-regular graph on N-vertices and G₂ a D₂-regular graph on D₁-vertices. Replacing each vertex in G₁ with a copy of G₂, we create an edge in this resulting graph on [N] × [D₁] by adding an edge for every path of length 3 of the following form:

(1) Take a random step inside a copy of G₂
(2) Take an edge inside G₁ which represents the jump from the current embedded G₂ to another.
(3) Take a random step inside the copy of G₂

Thus, an edge between vertex i and j exists if there is some verticies i' and j' such that there is an edge between i and i' in am embedded copy of G₂, an edge in the tensor product between i' and j', and an edge in an embedded copy of G₂ between j' and j.

This can be expressed formally via the rotation map of G, G₁, and G₂ as follows:

Let v ∈ [N], k ∈ [D₁], and i,j ∈ [D₂].
Let (k', i') = R_G₂(k,i), the first step within a cloud.
Let (w, l') = R_G₁(v, k), the step in G₁.
Let (l, j') = R_G₂(l' j), the second step within a cloud.

Then R_G( (v,k), (i,j)) = ((w,l), (j',i')).

The point of exploring the zig-zag product is that if the two graphs G₁ and G₂ are good expanders we expect that their product G will also be a good expander.

To this end, we have Theorem 4 which follows. Let G₁ be a (N, D₁, λ₁) graph and G₂ be a (D₁, D₂, λ₂) graph. Then the zig-zag G of G₁ and G₂ is (N · D₁, D₂², f( λ₁, λ₂ )) where f( λ₁, λ₂ ) ≤ λ₁ + λ₂ + λ₂² and f( λ₁, λ₂ ) < 1 if λ₁, λ₂ < 1.

Intuitively, we can think of the construction as trying evenly distribute entropy thoughout the resulting graph. We claim that a step in the zig-zag results in a more uniform distribution of the entropy given that the entropy was not already uniformly distributed. To see this we consider two cases based on the initial probability distribution.

If the distributions are not too close to uniform then the random first step used to produce an edge in the zig-zag contributes some amount of entropy. As the deterministic step across clouds and the following random step cannot decrease the contribution from step one, some amount of reallocation is done making the graph entropy more uniform.

If instead the entropy is close to uniform then the first step is unproductive. However the deterministic step is now effectively random due to the uniformity of the choice of vertex in the cloud and so a contribution is still made for the resulting step in the zig-zag.

The proof follows along the lines of considering any action in terms of its component breakdown into the above two cases, making use of the above propositions. While I believe I understand the intuition behind the idea, the algebraic manipulation seems a bit tedious for this post.

Some updates

2005-09-27T14:38:00.000-07:00

So far we have seen a few different definitions of expanders (edge expansion, vertex expansion, spectral expansion with second largest or second largest in absolute value eigenvalue), some mixing properties and its applications to reducing the number of random bits used in a BPP algorithm. Kevin presented quantitative connections between the various definitions. Last week we had Erin present the first zig-zag paper. This week David will present the second zig-zag paper on "lossless" (bipartite) expanders.

Coming up are applications of expanders. Some of you have already signed up for some topics. (The sign-up process has been a little ad hoc. The dates below are a little flexible, especially for the last few presentations; if anyone who hasn't signed up for a presentation wants to take one of the following dates -- or topics -- let me know ASAP.)

Oct 5, 7: Mike will present a cryptographic application, of amplifying the hardness of inverting a "one-way function."

Oct 12, 14: Phil will present some results on "extractors," which are devices used for refining "imperfect" sources of randomness to obtain "pure randomness." (We will see some of this in David's presentation, but won't have enough time to do justice to the topic at that point.)

Oct 19, 21: Hemanta will present a log-space algorithm for undirected connectivity in graphs (the celebrated SL=L result).

Oct 26, 28: Reza will present Irit Dinur's proof of the PCP theorem.

That leaves Chris, Nitish and Tracy for November. I'll get you some choices for what to present.

Be careful with < and >

2005-09-21T08:27:00.000-07:00

The first version of my last post didn't come out so well. Basically, using "< u" (without the space) started an underline and "< x" (without the space) disappeared. In retrospect, using notation other than < , > for inner product is probably a good idea since html uses greater than and less than for tags. (Using & followed by "lang" and "rang" probably would have also worked...)

Last week: Eigenvalues and expansion

2005-09-21T08:07:00.000-07:00

Last week, Kevin showed how two measures of graph expansion are related to the size the second largest eigenvalue.

On Wednesday, we talked about edge expansion. This is denoted h(G) and is the min (over all sets B containing at most half the vertices) of the number of edges between B and its complement divided by the size of B.

The main result for the day was showing

(d-λ)/2 ≤ h(G) ≤ sqrt(2d(d-λ))

for a d-regular graph whose adjacency matrix has second largest eignvalue λ (the largest eigenvalue is always d). This implies that a family of graphs has constant edge expansion if
and only if there is a constant gap between d and λ.

Before approaching the main result, we showed a couple of technical lemmas based on the Laplacian L(G) of a graph G. For a d-regular n-vertex graph, L(G)=dI-A(G), where A(G) is the adjacency matrix. It is not hard to show that L(G) has the same eigenvectors as A(G), but that the eigenvalues are shifted so that eigenvalue μ corresponds to eigenvector v in A(G), eigenvalue (d-μ) corresponds to v in L(G). In addition, for any vector ⟨x, x,Lx⟩ is the sum of
(x_i-x_j)² for each edge (v_i,v_j) in the corresponding graph. (Note that we are using ⟨u,v⟩ to denote the inner product of vectors u and v.)

Now for the first half of the main result ((d-λ)/2 ≤ h(G)):

The bulk of the work is done by the following theorem:

Th. If G is an n-vertex d-regular graph and B,C partitions its vertices, then
e(B,C) ≥ (1/n)(d-λ) |B| |C|.

Kevin presented a proof from the Probabilistic Method by Alon & Spencer. The main idea is to create a vector x based on the partition into B and C. Those elements corresponding to members of B are given value |C| and those corresponding to members of C are given value -|B|. Then we look at ⟨x,Lx⟩. By writing x in terms of an orthonormal eigenbasis and using the definition of inner product, we are able to show that this is at least (d-λ)⟨x,x⟩. Then we use the technical lemma relating to ⟨x,Lx⟩ and notice that non-zero terms in the resulting sum correspond to edges between B and C. The result
follows quickly by algebra.

(d-λ)/2 ≤ h(G) follows quickly from the theorem by assuming B is a set of size at most n/2 and letting C be the complement of B.

Now for the second half of the main result (h(G) ≤ sqrt(2d(d-λ))):

The main work for this is done by the following:

Lemma: If G is an n-vertex, d-regular graph whose vertices have non-negative weights where the weight vector is not zero but at least half the weights are 0, then h(G) is at most
(sum_{edges (v_i,v_j)} |w_i-w_j|)/(sum_{v_i} w_i)

(Try saying that 3 times fast...)

To prove this, we arrange the vertices in order of non-increasing weight and group the total weight by the contribution of edges between v₁ thru v_i and v_i+1 thru v_n.

To apply it and prove h(G) ≤ sqrt(2d(d-λ)), we need to find a weight vector. To do this, we take an eigenvector of L corresponding to λ orthogonal to the uniform vector. Without loss of generality, we assume that half its coordinates are at most zero. To get the vector of weights we take this eigenvector, zero the negative coordinates, and square each coordinate. Applying the Lemma and making a series of algebraic steps gives the desired result.

For Friday, we talked about vertex expansion. We say that a graph has (α,β)-vertex expansion if every subset S of size at most αn has at least β|S| neighbors. (Instead of counting the number of outgoing edges, we're counting the number of neighbors.) There are two main results, both for n-vertex d-regular graphs:

1. The vertex expansion is (α,1/((1-α)Θ²+α))
for 0≤α≤1, where Θ is (1/d) times the eigenvalue with second largest magnitude (the largest by magnitude other than λ₀=d).

2. A graph with (1/2,1+δ)-vertex expansion has λ ≤ d-δ²/(2d).

The first is proven by considering a subset S with size at most αn, looking at a uniform distribution over these vertices, and applying a series of identities (see below). The second (for which Kevin presented his own simplification) involved showing that δ≤h(G) and then using the second half of Wednesday's main result.

The algebraic identities used to prove these results are all quite straight-forward:

1. If G is an n-vertex d-regular graph with adjacency matrix A and
⟨x,1⟩=0, then
1a. ⟨x,Ax⟩ ≤ λ⟨x,x⟩
1b. ⟨Ax,Ax⟩ ≤ (dΘ)²⟨x,x⟩

(Proven similarly to one of the identities on Wednesday by rewriting x
in terms of an orthonormal eigenbasis.)

2. If π is a probability distribution over vertices of G and u is
the uniform vector with coordinates 1/n, ⟨π-u,u⟩=0.

(Proven by breaking ⟨π-u,u⟩ into ⟨π,u⟩-⟨u,u⟩.)

3. ⟨π,π⟩=1/n + ⟨π-u,π-u⟩

(Proven by breaking ⟨π-u,π-u⟩ into ⟨π,π⟩-2⟨π,u⟩+⟨u,u⟩.)

4. ⟨π,π⟩ ≥ 1/support(π), where support(π) is the number
of non-zero coordinates of π.

(Proven by considering the distribution over vertices counted in the support and applying the previous identity.)

I followed most of the steps in the proofs, but don't feel like I have any intuition about these arguments or ideas about how to improve the results.

A handy link

2005-09-12T16:21:00.000-07:00

Here's a link Manoj sent to me which has help for how to type math nicely on the blog.

http://www.w3.org/Arena/tour/symbols.html

Last week in class...

2005-09-11T23:14:00.000-07:00

Recap of previous results:

The lecture on 9/7 began with a recap of several definitions and results. Suppose that G is a d-regular expander graph, and λ is the second largest eigenvalue of the adjacency matrix A for G. (The largest eigenvalue will always be d, because it is a d-regular graph.) Let α be λ/d. This is the second largest eigenvalue of the normalized matrix M = 1/dA, which we will use for doing walks on the graph later.

The Expander-Mixing Lemma says: Given S and T which are subsets of the vertex set of G, E(S,T) - (d/n)ST ≤ λ (ST)^1/2. To interpret this, think of a random graph, where we'd expect an edge to be present with probability d/n. There are ST of these edges possible, so we'd expect dST/n edges between S and T. So we're saying here that the number of edges between S and T in an expander is very close to the number of edges in a random graph.

Application 1: Deterministic Error Amplification for BPP algorithms - See Linial-Wigderson notes, lecture 2, section 4.1

The first application covered is using the E-M Lemma to improve a BPP algorithm. Given some algorithm A which tests membership in a language in BPP, we create a new algorithm A'. A' considers an expander graph on the set of possible m-bit strings that the algorithm A might use. It first picks some random m-bit string r, and then runs algorithm A on x with r and all of r's neighbors in the graph. It then outputs the majority opinion answer for x.

We now must bound the probability that A' is wrong. For A' to be wrong, more than half of r's neighbors must be bad, in that they return the wrong answer. If we let S be the set of strings that give a wrong answer for A' and T be the set of strings that give a wrong answer for A, we can use the E-M Lemma to bound the number of edges and do some inequality manipulation to get a probability of failure ≤ O(1/d). So using the same number of random bits, we have a probability that is O(1/d) instead of constant.

Random Walks and Markov Chains:

We now let p be a probability vector on the vertices of the graph G, and M be the normalized matrix for A as defined above. We can consider the operation Mp, which simulates taking a step in the graph along a random edge from your current location (represented by the probability vector p). Then for a random walk, we let p^(t) = M^t p, which is the probability after t random steps are taken.

Let u be the uniform vector [1/n 1/n ... 1/n]^T, which represents the uniform distribution on a graph. For an expander graph, we get that p^(t) - u ₂&le &alpha^t. Intuitively, this means that we move quickly towards the uniform distribution, since in an expander the second largest eigenvalue is generally much smaller than the largest eigenvalue (which is 1). So M is somehow greatly increasing the component of p which is the uniform distribution (which corresponds to the largest eigenvalue) while shrinking all other components (which correspond to the much smaller other eigenvalues).

To prove this fact, we simply consider one step Mp. If we split p into 2 components, one of which is the uniform component, we can bound the second component by the second largest eigenvalue since all other components are altered by at most that value. Iterating this for t steps gives the bound α^t.

Application 2: Random walks for RP algorithms - See Linial-Wigderson notes, Lecture 3, section 3.1

We do another error reduction application, this time for an RP algorithm A. We create our new algorithm A' by picking a random vertex in the space of random strings, and then doing a random walk in the expander graph on this space of strings. We call A(x) for every random string we land on. If all of the strings agree that x is in L, we accept x. If any report x is not in L, we reject x.

In order for A' to be wrong, our entire walk must stay within the set of strings that A breaks on. To bound this value, we do a random walk in the graph but at each step cancel out all the probabilities that leave the bad region and continue the walk on the subset still in the bad region. In terms of the linear algebra involved, all we need to do is multiply by a characteristic vector for the bad region, where each vertex in the bad region has a 1 and all others have a 0 in the vector. In the end, the probability of the walk staying entirely in the region that A will be wrong on is ≤ (α + β)^t in a t step walk.

Our algorithm uses m + t log d bits of randomness to get a bound of (α + β)^t. Compare this to the algorithm that simply picks t random m-bit strings. We would use mt random bits, and get a bound of β^t. So we achieve a similar bound while using far fewer random bits.

Application 3: Back to BPP algorithms - See Linial-Wigderson, lecture 3, section 3.1

We now return to our BPP algorithm A. In the first application, we just looked at a node and its neighbors, but using our new tools, we will now analyze the same algorithm where we take a random walk of length t in our expander instead of just looking at the neighbors of our initial vertex.

To bound the probability that this fails, we have to compute the probability that in a t step random walk, more than half of the vertices are in the bad region, where our algorithm A is incorrect. To calculate this, we consider a subwalk of size ≥ t/2, where each "step" is between two m-bit strings that A fails on. Each new "step" will be a matrix Mⁱ, with i ≥ 1. In terms of eigenvalues, this means that the 2nd largest eigenvalue of Mⁱ will be &alphaⁱ, which is always ≤ α. Therefore, we get a bound on our failure of (α + β)^t/2. Now going back to the larger walk, we notice that there are 2^t walks total, and each is bad with probability ≤ (α + β)^t/2, so the probability of getting a bad walk is &le 2^t(α + β)^t/2. Since α and β can be chosen to be less than 1/16, we get a total bound of ≤ c^t/2, where c<1.

Application 4: Harness of Approximation - See Linial-Wigderson notes, lecture 3, section 4

There is a result based on the PCP Theorem which states that there exists an a and b with 0 < a < b < 1 such that we cannot tell if ω(G) ≤ an or ω(G) ≥ bn, where n is the number of vertices in G and ω(G) is the size of the largest clique in G. Assuming this result, is it possible to use expanders to show that it is hard to approximate &omega(G) to within n^ε for some ε > 0.

The construction for this consisting of creating the randomized graph product, G^k. This graph has a vertex for every k-walk in the original grpah G. An edge exists between two vertices if the 2 k-walks were within a common clique in G. By taking a random sample from this new graph, we saw that if there was a N^ε approximation for the sampled graph, then we could distinguish between ω(G) &le an and ω(G) ≥ bn.

Next presentations

2005-09-07T15:29:00.000-07:00

I forgot to mention this in the class today.

After Kevin presents the connections between spectrum
and expansion, the next topic I'd like to see covered
is some constructions of expanders.

If you read Sariel's recent blog entry you would have
noticed something about zig-zag products. So we need
*two* volunteers to find out if they are indeed related
to clothing as Sariel claims. Two, because there are
two papers on zig-zag products:

Reingold, Vadhan and Wigderson (2000) and
Capalbo, Reingold, Vadhan and Wigderson (2002)

Both are very beautiful papers, and also contain lot of
intuition that will be of use to us later on.

Please send me a mail if you think your life wouldn't
be complete without presenting one of these papers! On
Friday, we'll finalize who's presenting which one.

Eigenlectures

2005-09-02T22:37:00.000-07:00

In the last two lectures we covered some very basic linear algebra we'll use to study expanders. We chose our topics mostly following Lecture 2 from the Linial-Wigderson course. Restricting to undirected graphs makes the linear algebra involved very simple (and beautiful, I must say) for us. Some of the things we saw are:

A graph G defines a linear transform, namely multiplication by its adjacency matrix A. This transform naturally corresponds to how a probability distribution on the nodes of the graph gets transformed in a single step of the (natural) random walk defined on G. (But now that we have a linear transform in our hands, we need not restrict ourselves to applying it to probability distributions. Any real vector is fair game.)

We'll consider undirected graphs. Then the adjacency matrix A is symmetric (and of course real). Then it can be shown¹ that A=P^TDP, where D is a diagonal matrix and P is an orthonormal matrix (all real). In plain English that means, in some (orthonormal) basis (defined by the rows of P), A is a transformation which simply scales each dimension independently. This change of basis is extremely useful (as we saw in the proof of the "Expander Mixing Lemma").

Rows of P are "eigenvectors" of A, with corresponding "eigenvalues" being the diagonal entries of D.²Most of what we talked in the class about real symmetric matrices becomes fairly intuitive once we look at D instead of A. One of those intuitive things is the characterization of the spectrum using Rayleigh quotients. Since a Rayleigh quotient is defined geometrically (using angles, lengths etc., with no reference to any particular basis), and the same is true for eigenvalues, it is all right to think of D instead of A.

Writing A=P^TDP is the same as the "spectral decomposition," A=Σλ_iP_i. Here λ_i is the i-th diagonal entry of D and P_i=v_iv_i^T is the linear transformation which returns the component along v_i, the i-th row of P.

For d-regular (connected, non-bipartite) graphs, we saw that λ₀ = d, and |λ_i|<d for i>0.

We analyzed the eigenvalues and eigenvectors of our favorite examples, the clique (with self-loops) and the cycle. The clique has a single non-zero eigenvalue (=n). Then we saw that any d-regular graph has a d/n "component" of the clique in it. An ideal expander would behave as if it didn't have any othercomponents.

We also saw some relations between the spectral gap and the expansion of a graph. Kevin will talk more about this the week after the next.

______

^1.The proof mentioned above uses induction and is simple, but is not quite "elementary," because it refers to the existence of at least one real eigenvalue for A. The short proof for that depends on the Fundamental Theorem of Algebra, which I'm sure everyone considers second nature, but I don't think is quite what an elementary proof for the above statement should contain. So, if anyone out there can give (pointers to) a simple(r) proof for the spectral decomposition theorem, but restricted to real symmetric matrices, that would be great.

^2. The concept of eigenvalues/eigenvectors is not restricted to linear transforms defined by real symmetric matrices. A typical linear algebraic exposition would first introduce you to eigenvalues/eigenvectors for general linear transforms and then specialize it to real symmetric matrices. To keep our focus, and to keep things simple, we started directly with real symmetric matrices. But beware that the nice behavior described above does not hold in general.

ps: I'm having some very strange problems with the way Firefox is rendering things in my newly acquired powerbook (OS X 10.4). I hope things show up nicely in your browsers... update: fixed it!

Course-blog for CS 598MAN

2005-08-26T12:54:00.000-07:00

This is the course-blog for an introductory graduate course on Expanders offered by the theory group at UIUC Computer Science.

We had our first (introductory) lecture today. I'll put up a few things here and we'll get started shortly...