## Lecture 8: Confining a random walk on an expander is hard

Let be an -spectral expander, be a subset of vertices of of size . Suppose we uniformly choose a random vertex of and walk randomly for steps.

**Theorem 1 (Confining a random walk is hard). **Let be the event that the walk is confined within the entire time.Then, Prob. In particular, if then this confinement probability is exponentially small.

*Proof.* Let be the “*projection into matrix*“, i.e. and for all other . Noting that is idempotent, it is not difficult to see that

Prob

Thus, to bound Prob we need to know how much the matrix *shrinks *a vector after each multiplication. The same trick we did in the last lecture gives, for any non-zero vector

Now, consider any non-zero vector . Let . Then, . First, express as a linear combination of the orthonormal eigenvectors of :

Let and . Then,

The usual trick gives

By Cauchy-Schwarz, , we conclude that

Consequently, each time we apply to a vector we reduce its length by a ratio of at least . There are applications, and the initial vector has length . The theorem follows.

**Theorem 2 (Saving random bits for RP).** A language is in the class RP if there exists a polynomial time randomized algorithm satisfying the following conditions:

- Prob accepts
- Prob accepts

Suppose uses random bits. To reduce the error probability to , the easy way is to run the algorithm times and accept the input if the algorithm accepts it at least once. However, this approach requires random bits. By imposing a (strongly explicit) -spectral expander on the space of random strings of length , we can obtain the same effect with only random bits. Here, we require . A strongly explicit expander is an expander which, given a vertex, there’s a poly-time algorithm computing the neighboring vertices.

## Some linear algebra

I mentioned the Perron-Frobenius theorem in the lecture. There are two versions of the theorem, one for positive matrices and one for non-negative matrices. Define the *spectral radius* , where the max goes over all eigenvalues of . Here is the modulus of , as we allow complex eigenvalues.

**Theorem 1 (Perron-Frobenius, positive matrices).** Let be the spectral radius of a positive matrix . Then,

- is positive
- is an (real) eigenvalue of
- there exists a positive -eigenvector , i.e.
- has geometric and algebraic multiplicity , i.e. is a single root of and the -eigenspace has dimension
- for all other eigenvalues of , i.e. is the unique eigenvalue of maximum modulus

**Theorem 2 (Perron-Frobenius, non-negative matrices). **Let be the spectral radius of a non-negative matrix . Then,

- is non-negative
- is an (real) eigenvalue of
- there exists a non-negative -eigenvector , i.e.

Theorem 2 follows from Theorem 1 by a perturbing the non-negative matrix (so that it becomes positive), then take a limit. See my favourite linear algebra book for the proofs of these theorems.

## Lecture 7: Random walks on expanders are rapidly mixing

Let be the normalized adjacency matrix of a -regular graph, be the eigenvalues of this matrix, and define .

Suppose we take a random walk on starting from an initial distribution . Then, the distribution after steps is . Using the spectral theorem, it is not difficult to prove that, if then , where is the uniform distribution. The more difficult question is “how fast is the walk converging to this limit?”

To answer this question, we need to define a notion of *distance* between two distributions. The total variation distance is probably the most commonly used. Since we are working on a finite probability space, the total variation distance is half the -norm. Thus, we would like a theorem bounding the rate at which tends to zero. We proved that

**Theorem 1 (Convergence in )**

**Theorem 2 (Convergence in )**

Theorem 1 follows from Theorem 2 by the Cauchy-Schwarz inequality. To prove Theorem 2, note that

Where, is perpendicular to and . Each time we apply to a vector perpendicular to (its first eigenvector), we *shrink* the length of by a factor of at least . Hence the theorem follows.

An -spectral expander is a -regular graph on vertices such that . If then an -spectral expander certainly has spectral gap bounded away from zero. Conversely, a graph whose spectral gap is bounded away from zero (plus self-loops) is a spectral expander.

## Lecture 6: Cheeger-Alon-Milman Inequality

**1**. We showed that Gap-Max-3SAT is NP-Hard for some constants using -edge expanders ( is a constant). The proof relies on the fact that such an expander can be constructed in polynomial time. In the last lecture, we only proved that such expanders exist for all sufficiently large , but we have not discussed how to construct expanders in polynomial time yet. Efficient constructions of good expanders will be discussed probably next week.

**2**. We proved half of the so-called Cheeger-Alon-Milman inequality, which states that

for any -regular graph . Here, is the second largest eigenvalue and is the edge-isoperimetric number of the graph. We showed only that . Briefly, the proof went as follows.

First, we “symmetrize” .

Define the sparsity of to be

Then, we just showed that . It remains to show that . To do so, we turn the expression for into a more algebraic form. Imagine assigning a value of 1 to each vertex in and 0 to each vertex in , we get a vector . It is not difficult to see that

So, is the objective value of a certain optimization problem over zero-one vectors in . If we relax the zero-one condition, we get a lower bound for . Specifically,

Now, subtract (or add) the same amount from (to) each will not change the min. Hence, we can replace each vector by where . This way, , or simply . Consequently,

Now, let be the adjacency matrix of , then it can be verified straightforwardly that

Moreover, if , then . Consequently,

For a more elaborate discussion on Cheeger-Alon-Milman inequality, see a nice series of posts by Luca Trevisan on the topic.

## Lecture 5: Expanders, Probabilistic Proof of Existence

We gave a proof showing that most regular graphs are good (edge/vertex) expanders. In terms of edge-expansion, Bella Bollobas in this paper showed that, for every , most random -regular graphs have edge-expansion rate (i.e. edge-isoperimetric number) at least for some constant . (Specifically, we can set . On the other hand, given any -regular graph of order , if we select a random subset of vertices of size , then the expected number of edges crossing the cut is

So the edge-isoperimetric number is bounded above by . Thus, for large graphs the edge expansion rate is (roughly) at most .

Better yet, Noga Alon proved in this paper that there is a constant such that the edge-isoperimetric number of any -regular graph (with sufficiently large number of vertices) is at most .

In summary, we can roughly think of edge-isoperimetric numbers of random -regular graphs to be about .

For small values of , Bollobas’ analysis yields the following. For every sufficiently large ,

- there exists a -edge expander
- there exists a -edge expander
- there exists a -edge expander
- there exists a -edge expander
- there exists a -edge expander

## Lecture 4: Proof that PCP Theorem is equivalent to hardness of Gap-Max-SAT

In today’s lecture, I proved that the PCP theorem is equivalent to the fact that

- Gap-MaxE3SAT is NP-Hard for some constant

From the fact, it’s easy to show that

- MaxE3SAT is NP-Hard to approximate to within some constant

I also outlined things that will be discussed about expanders.

## Lecture 3: Outline of Dinur’s Proof

In today’s lecture, I discussed the following:

- A list of results regarding various PCPs following the outline in Madhu Sudan’s lecture notes (See Section 2.2. on History of Results).
- Mentioned that the PCP theorem is equivalent to the NP-Hardness of Gap-MaxE3SAT for some constant , which is equivalent to the NP-Hardness of approximating MaxE3SAT to a certain constant ratio .
- Defined the so-called Gap-Max-CG- problem, whose NP-Hardness is also equivalent to the PCP theorem
- Briefly showed one direction of the PCP theorem, namely PCP[O(log n), O(1)] NP
- Outlined Dinur’s proof of the PCP theorem.

Another article of interest is from Radnakrishnan and Sudan.

On Monday, I will prove #2 above formally, and start talking about expanders.

leave a comment