## 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.

## Lecture 2: The two views of PCP

In today’s lecture, we saw more on the prover-verifier view of the PCPs and approximation algorithms. We also briefly heard some hand-wavy reasons why we should expects codes to prop up in the proof of the PCP theorem.

Next lecture, Hung will connect these two “disparate” view and give an overview of the main steps in Dinur’s proof.

## Lecture 1: Introduction

In today’s lecture, we saw two “disparate” interpretations of languages in NP: in particular, the proof-verifier definition of NP (and PCPs) and approximation algorithms for NP-complete problems (3ESAT in particular). We also saw the statement of the wonderful and mysterious PCP theorem.

Next lecture, we will wrap up some left over discussion about these two views and then go on to show that the views are actually the same.

Today’s lecture was based on these lecture notes.

Also in class I mentioned that the PCP theorem has an very interesting history. For a very nice description, see this writeup by Ryan O’Donnell.

leave a comment