They are perfect for each other

Now that Ted Cruz has chosen his running mate, everybody is wondering: who is going to be Trump’s pick for vice-president?

It would make sense if, to mitigate his negatives, Trump chose a person of color and someone who has a history of speaking out against income inequality.

He or she would have to be someone who is media-savvy and with some experience running a campaign, but definitely not a career politician. And of course he or she should be someone who endorsed Trump early on, like, say, in January.

Continue reading

CS294 Lecture 18: Margulis-Gabber-Galil Expanders

In which we present an algebraic construction of expanders.

1. The Marguli-Gabber-Galil Expanders

We present a construction of expander graphs due to Margulis, which was the first explicit construction of expanders, and its analysis due to Gabber and Galil. The analysis presented here includes later simplifications, and it follows an exposition of James Lee.

Continue reading

CS294 Lecture 16: Zig-Zag Graph Product

In which we give an explicit construction of expander graphs of polylogarithmic degree, state the properties of the zig-zag product of graphs, and provide an explicit construction of a family of constant-degree expanders using the zig-zag product and the polylogarithmic-degree construction.

A family of expanders is a family of graphs {G_n = (V_n,E_n)}, {|V_n|=n}, such that each graph is {d_n}-regular, and the edge-expansion of each graph is at least {h}, for an absolute constant {h} independent of {n}. Ideally, we would like to have such a construction for each {n}, although it is usually enough for most applications that, for some constant {c} and every {k}, there is an {n} for which the construction applies in the interval {\{ k, k+1, \ldots, ck \}}, or even the interval {\{ k, \ldots, ck^c\}}. We would also like the degree {d_n} to be slowly growing in {n} and, ideally, to be bounded above by an explicit constant. Today we will see a simple construction in which {d_n = O(\log^2 n)} and a more complicated one in which {d_n = O(1)}.

Continue reading

CS294 Lecture 15: Abelian Cayley graphs

In which we show how to find the eigenvalues and eigenvectors of Cayley graphs of Abelian groups, we find tight examples for various results that we proved in earlier lectures, and, along the way, we develop the general theory of harmonic analysis which includes the Fourier transform of periodic functions of a real variable, the discrete Fourier transform of periodic functions of an integer variable, and the Walsh transform of Boolean functions.

Earlier, we prove the Cheeger inequalities

\displaystyle  \frac{\lambda_2}{2} \leq \phi(G) \leq \sqrt{2 \lambda_2}

and the fact that Fiedler’s algorithm, when given an eigenvector of {\lambda_2}, finds a cut {(S,V-S)} such that {\phi(S,V-S) \leq 2\sqrt{\phi(G)}}. We will show that all such results are tight, up to constants, by proving that

  • The dimension-{d} hypercube {H_d} has {\lambda_2 = 1- \frac 2d} and {h(H_d) = \frac 1d}, giving an infinite family of graphs for which {\frac{\lambda_2}{2} = \phi(G)}, showing that the first Cheeger inequality is exactly tight.
  • The {n}-cycle {C_n} has {\lambda_2 = O(n^{-2})}, and {\phi(C_n) = \frac 2n}, giving an infinite family of graphs for which {\phi(G) = \Omega(\sqrt{\lambda_2})}, showing that the second Cheeger inequality is tight up to a constant.
  • There is an eigenvector of the 2nd eigenvalue of the hypercube {H_d}, such that Fiedler’s algorithm, given such a vector, outputs a cut {(S,V-S)} of expansion {\phi(S,V-S) = \Omega(1/\sqrt{d})}, showing that the analysis of the Fiedler’s algorithm is tight up to a constant.

In this lecture we will develop some theoretical machinery to find the eigenvalues and eigenvectors of Cayley graphs of finite Abelian groups, a class of graphs that includes the cycle and the hypercube, among several other interesting examples. This theory will also be useful later, as a starting point to talk about constructions of expanders.

For readers familiar with the Fourier analysis of Boolean functions, or the discrete Fourier analysis of functions {f: {\mathbb Z}/N{\mathbb Z} \rightarrow {\mathbb C}}, or the standard Fourier analysis of periodic real functions, this theory will give a more general, and hopefully interesting, way to look at what they already know.

Continue reading

CS 294 Lecture 14: ARV Analysis, Part 3

In which we complete the analysis of the ARV rounding algorithm

We are finally going to complete the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio {O(\sqrt {\log |V|})}.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

Continue reading

CS294 Lecture 13: ARV Analysis, cont’d

In which we continue the analysis of the ARV rounding algorithm

We are continuing the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio {O(\sqrt {\log |V|})}.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

Continue reading

CS294 Lecture 12: ARV Analysis

In which we begin the analysis of the ARV rounding algorithm

We want to prove

Lemma 1 (ARV Main Lemma) Let {d} be a negative-type metric over a set {V} such that the points are contained in a unit ball and have constant average distance, that is,

  • there is a vertex {z} such that {d(v,z)\leq 1} for every {v\in V}
  • {\sum_{u,v\in V} d(u,v) \geq c\cdot |V|^2}

Then there are sets {S,T \subseteq V} such that

  • {|S|, |T| \geq \Omega(|V|)};
  • for every {u\in S} and every {v\in T}, {d(u,v) \geq 1/{O(\sqrt {\log |V|})}}

where the multiplicative factors hidden in the {O(\cdot)} and {\Omega(\cdot)} notations depend only on {c}.

In this lecture, we will show how to reduce the ARV Main Lemma to a statement of the following form: if {\{ {\bf x}_v \}_{v\in V}} is a set of vectors such that the metric {d(\cdot, \cdot)} in the ARV Main Lemma can be written as {d(u,v) = || {\bf x}_u - {\bf x}_v ||^2}, and {{\bf g}} is a random Gaussian vectors, and if {\ell} is such that with {\Omega(1)} probability, there are {\Omega(n)} disjoint pairs {u,v} such that {d(u,v) < \ell} and {| \langle g, {\bf x}_u\rangle - \langle g, {\bf x}_v \rangle | \geq \Omega(1)}, then {\ell \geq \Omega(1/\sqrt{\log n})}. We will then prove such a statement in the next lecture.

Continue reading