Analysis and Design of Algorithms

1 Probability Bounds

Markov Inequality

For a nonnegative random variable $X$, for any $k>0$,

$$\mathrm{Pr}\left(X\ge k\right)\le \frac{𝔼(X)}{k}$$ (1)

If we have the variance of a random variable, we can apply more detailed analyses:

Chebyshev Inequality

Let $X$ be a random variable with $𝔼(X)=\mu$ and $Var(X)={\sigma }^2$, then

$$\mathrm{Pr}\left(|X-\mu |\ge t\right)\le \frac{{\sigma }^2}{t^2}.$$ (2)

The proof is straightforward after applying Markov inequality to $|X-\mu |$.

Chernoff Bound

Let $W_i$ be independent random variables. $W=W_1+\mathrm{\cdots }+W_n$. Chernoff bound takes advantage of higher-order conditions of independent variables. For Bernoulli random variables with probability $p$,

$$\mathrm{Pr}\left(W\ge (1+\delta )𝔼[W]\right)\le {\left(\frac{e^{\delta }}{{(1+\delta )}^{\delta }}\right)}^{\mu }$$ (3)

For $X_i\in [0,1]$

$$[Pr(X\ge (1+\delta )\mu )]\le {\exp }^{-\frac{{\delta }^2\mu }{3}},[Pr(X\le (1-\delta )\mu )]\le {\exp }^{-\frac{{\delta }^2\mu }{2}},\mathrm{Pr}[X\ge R]\le {\exp }^{-R},\text{for}R\ge 5\mu$$ (4)

The proof is by considering the random variable $e^{tW}$, which contains higher-order information of $W$.

1.1 An Example: Median Finding

Goal:

• Input a set $S$ of integers

• Find the median $m\in S$: at least $\lceil \frac{n}{2}\rceil$ elements $\le m$ and at least $\lfloor \frac{n}{2}\rfloor +1$ elements $\ge m$.

We want to find $d,u\in S$, such that $d\le m\le u$, with $C=\{s\in S,d\le s\le u\}$ small enough. Specifically, we do

• Count number of elements in $S$ larger than $u$, and smaller than $d$.

• Sort $C$ in $O(|C|\log |C|)=o(n)$ time.

• Deduce the median.

How to choose $C$? We first select a multi-set $R$ of $n^{3/4}$ elements iid from $S$, and sort $R$.

• Let $d$ be the $\frac{1}{2}{n}^{3/4}-\sqrt{n}$ smallest element and $u$ be the $\frac{1}{2}{n}^{3/4}+\sqrt{n}$ smallest one.

• Compute . If $|L_d|$ or $|L_u|\ge \frac{n}{2}$, we fail. If $|C|>4n^{3/4}$, we fail.

• Otherwise, we sort $C$ and return the $\frac{n}{2}-|L_d|$ smallest element in $C$.

The runtime is $O(n)$ indeed, but we have to bound the probability of failure.

. If $Y_1=0$, then $|L_d|\le \frac{1}{2}$.

. If $Y_2=0$ then $|L_u|\le \frac{1}{2}$.

$Y_3=\mathrm{𝟙}\{|C|>4n^{3/4}\}$.

$\mathrm{Pr}\left(Y_1=1\right)\le \frac{1}{4n^{1/4}}$ by applying Chebyshev bound. (Could get better bound if using Chernoff bound?)

$\mathrm{Pr}\left(Y_3=1\right)\le \frac{1}{2n^{1/4}}$. Either $2n^{3/4}$ elements larger than $m$ or $2n^{3/4}$ elements smaller than $m$. Suppose the first happens, then $R$ has at least $\frac{1}{2}{n}^{3/4}-\sqrt{n}$ samples that are among the $\frac{1}{2}n-2n^{3/4}$ largest elements in $S$. (Consider the rightmost interval in $R$.) Let $R={\{a_i\}}_{i=1}^{n^{3/4}}$, and $X_i=1$ if $a_i$ is larger than the $\frac{1}{2}n+2n^{3/4}$ element. $𝔼(X_i)=\frac{1}{2}-2n^{-1/4}$. $𝔼(\sum X_i)=\frac{1}{2}{n}^{3/4}-2\sqrt{n}$. Then

$$\mathrm{Pr}\left(\sum _{i=1}^{n^{3/4}}{X}_i\ge \frac{1}{2}{n}^{3/4}-\sqrt{n}\right)\le \frac{1}{2}{n}^{-1/4}$$ (5)

By union bound, we fail with probability less than $n^{-1/4}$.

2 Flows

A graph $G=(V,E)$. Compute its maximal flow.

Ford-Fulkerson algorithm $O(mF)$, where $F=C\cdot {\mathrm{\Delta }}_s$, $C$ is the largest flow capacity.

Edmands Karp $O(m^{2}n)$.

Theorem 2.1.

The maximal flow from $s$ to $t$ equals the min-cut that separates $s,t$.

Note: Recursively reducing paths from $s$ to $t$ gives the maximal flow. In the end $s$ and $t$ will be disconnected, which naturally yields the solution for a Min-Cut.

2.1 Applications

Bipartite Matching Using max-flow algorithms to find maximum matching for bipartite matching.

Theorem 2.2 (Hall).

A bipartite graph has a perfect matching iff $\forall S\subseteq L$ or $S\subseteq R$, $|\mathrm{\Gamma }(S)|\ge |S|$, where $\mathrm{\Gamma }(S)$ is the set of neighbors of $S$.

Image Segmentation Let $f_i$ be the cost of assigning pixel $i$ to the foreground. $b_i$ is the cost of assigning it to the background. And $s_{ij}$ is the cost of separating $i$ and $j$.

$$\underset{S}{\min }\text{cost(S)}=\sum _{i\in S}{f}_i+\sum _{i\in S^C}{b}_i+\sum _{i\in S,j\in S^C}{s}_{ij}$$ (1)

This can be translated into a $s,t$ Min-cut problem.

2.2 Min-Cut

Instead of finding an $(s,t)$- Min-Cut, we find an $(S,S^C)$ partition of vertices $V$.

Karger’s randomized algorithm

Repeatedly contract two nodes together, randomly, until only two supernodes are left. The runtime would be $O(n^2)$. ($O(n)$ for each edge contraction.)

This randomized algorithm returns the correct answer with probability

$$p\ge \frac{1}{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}$$ (2)

Repeat $n^2\log n$ time, so the overall runtime would be $O(n^4\log n)$ time to achieve a $O(1/n^c)$ failure probability.

Proof Sketch..

When there are $t$ supernodes left, we have

$$\mathrm{Pr}[e\in \delta (S,S^C)]\le \frac{2}{t}$$ (3)

This is because each node must have degree $\ge k$ if the minimum cut is $k$.

Then we multiply the probability together, which yields the final bound. ∎

Corollary 2.3.

There are at most $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ number of min-cuts in a graph.

2.3 Complexity classes of BPP: randomized poly time

A randomized algorithm that runs in $poly(n)$ time, with correct probability $\ge \frac{2}{3}$ for any input $x$.

Boosting: Run an algorithm in BPP $n$ times independently and take a majority vote, then by Chernoff bound,

$$\mathrm{Pr}[Correct]\ge 1-\exp \left(-\frac{n}{48}\right).$$ (4)

3 Streaming Algorithms

Inputs coming in consistently. Cannot store all data. Need an online algorithm to deal with incoming data.

Setup.

Inputs: $\sigma =(s_1,s_2,\mathrm{\dots }{s}_m)$, where $s_j\in \{1,\mathrm{\dots },n\}$.

Assumption: The length of input $Len(m)$ is known, and the range is known.

Let $f_i=|\{1\le j\le m\}|s_j=i|$.

$F_0={\sum }_{i=1}^n{(f_i)}^0=\mathrm{\#}\text{of distinct elements}$, where $0^0=0$.

$F_1={\sum }_i{f}_i=m$, space complexity: $\log m$.

What about $F_2={\sum }_i{f}_i^2$? Can we find an algorithm with logarithmic space complexity?

3.1 Deterministic algorithm fails for $F_2$

Assume there exists a deterministic algorithm to compute $F_2$ exactly. We construct a stream:

$$((1,x_1),\mathrm{\dots },(n,x_n)),\text{where}x\in {\{0,1\}}^n$$ (5)

Run the algorithm. Assume the memory at the end is $m(x)\in {\{0,1\}}^S$.

We then initialize the memory to $m(x)$ and feed and $(i,0)$ to the algorithm. There are two possibilities:

• $F_2$ increases by 1, if $x_i=1$,

• $F_2$ increases by $2^2-1=3$, if $x_i=0$.

It’s possible to completely recover $x$ by $m(x)$, so $m(x)$ must have at least $2^n$ possible values. The space complexity is $\mathrm{\Omega }(n)$.

3.2 Randomized algorithm for $F_2$

Hash function $h:\{1,\mathrm{\dots },n\}\to \{1,-1\}$.

• Initialize: set $c=0$

• Process $s_j$: Add $h(s_j)$ to $c$.

• Return $c^2$.

Space: $-m\le c\le m$, so it takes $O(\log m)$ space.

We show that $Z=c^2$ is an unbiased estimation of $F_2$. For $j\in \{1,\mathrm{\dots },n\}$, let $Y_j=h(j)\in \{\pm 1\}$.

$$Z={(f_1{Y}_1+\mathrm{\cdots }+f_n{Y}_n)}^2$$ (6)

so

$$𝔼[Z]=\sum _{i=1}^n{f}_i𝔼{[Y_i]}^2+\sum _{i\ne j}{f}_i{f}_j𝔼(Y_i)𝔼(Y_j)=\sum _{i=1}^n{f}_i^2=F_2.$$ (7)

We now bound the variance of $Z$ to apply tail bounds.

$𝔼[Z^2]$ $={\displaystyle \sum _{i,j,k,l}}{f}_i{f}_j{f}_k{f}_l𝔼[Y_i]𝔼[Y_j]𝔼[Y_k]𝔼[Y_l]$ (8)

$={\displaystyle \sum _{i=1}^n}{f}_i^4𝔼[Y_i^4]+3{\displaystyle \sum _{i\ne j}}{f}_i^2{f}_j^2𝔼[Y_i^2]𝔼[Y_j^2]$ (9)

$=F_4+3(F_2^2-F_4),$ (10)

so $Var(Z)=2F_2^2-2F_4\le 2F_2^2$.

$$\mathrm{Pr}[|Z-F_2|\ge ϵF_2]\le \frac{2F_2^2}{{ϵ}^2{F}_2^2}=\frac{2}{{ϵ}^2}.$$ (11)

This bound is great, but not so satisfactory. Actually, using the median of means trick, we can get an exponential boost, i.e., a $(1\pm ϵ)$ w.p. at least $(1-\delta )$ using space $O(\frac{1}{{ϵ}^2}\log \left(1/\delta \right)\log m)$.

3.3 Derandomization

Definition 3.1.

A family of random varibles $(x_1,\mathrm{\dots },x_N)$ is called $k$-wise independent if for every $k$-tuple $(i_1,\mathrm{\dots },i_k)\in {\{1,\mathrm{\dots },N\}}^k$, $(x_{i_1},\mathrm{\dots },x_{i_k})$ are independent.

Specifically, when they are $N$-wise independent, it is called fully independent.

Remark. The randomized algorithm above does not need full independence. In fact, all we need is a $4$-wise independence (required in the analysis of variance). This is also the reason why we can construct such a hash function in $O(\log n)$ but not $O(n)$.

Definition 3.2.

A family $H$ of hash functions $h:A\to B$ is called $k$-wise independent if for any distinct points $x_1,\mathrm{\dots },x_k\in A$ and $i_1,\mathrm{\dots },i_k\in B$,

$${\mathrm{Pr}}_{h\in H}(h(x_1)=i_1,\mathrm{\dots },h(x_k)=i_k)=\frac{1}{{|B|}^k}.$$ (12)

3.4 Construction of $k$-wise independent hash functions

Let $A=B={\mathbb{Z}}_p:=\{0,1\mathrm{\dots },p-1\},$ where $p$ is a prime.

$$H_2=\{f_{a,b}:x\mapsto ax+bmodp,(a,b)\in {\mathbb{Z}}_p^2\}.$$ (13)

Then

$${\mathrm{Pr}}_{a,b}(a{x}_1+b=i_1\wedge a{x}_2+b=i_2)={\mathrm{Pr}}_{a,b}(a=\frac{i_2-i_1}{x_2-x_1}\wedge b=i_2-x_{2}a)=\frac{1}{p^2}.$$ (14)

So this is a 2-wise independent hash function family. We get $h(0),\mathrm{\dots },h(p)$ p random variables with $2\log p$ space.

We can extend to $x\mapsto {\sum }_{i=0}^{k-1}{a}_i{x}^{i}modp$ to create a $k$-wise independent hash function family, with space complexity of $k\log p$.

3.5 Algorithm for $F_0$.

Function $h:\{1,\mathrm{\dots },n\}\to \{1,\mathrm{\dots },n\}$.

• Initialize $c=0$

• Process $s_j$: Let $z$ be the largest power of 2 that divides $h(s_j)$. If $z>c$, $c\leftarrow z$.

• Return $2^{c+1/2}$.

Intuition:

If the stream has $d$ distinct elements, there is a good chance that one of the $d$ values of $h(s_j)$ will be divisible by $d$.

If there are no more than $d$ distinct elements, it’s unlikely that an $h(s_j)$ has more than $\log d$ zeros in a row.

$j=\{1,\mathrm{\dots },n\},r\ge 0$, $X_{r,j}:$ indicator random variable that $h(j)$ is divisible by $2^r$.

$Y_r={\sum }_{j:f_j>0}{X}_{r,j}$. So if $Y_r=0$, no elements have $r$ or more zeros, so $c\le r-1$.

$$𝔼[X_{r,j}]=\mathrm{Pr}\left(h(s_j)\text{ has r zeros}\right)=\frac{1}{2^r}.$$ (15)

so

$$𝔼[Y_r]=\frac{F_0}{2^r},Var(Y_r)=\sum _{j:f_j>0}Var(X_{r,j})=\frac{F_0}{2^r}.$$ (16)

$$\mathrm{Pr}[Y_r>0]\le \frac{F_0}{2^r},\mathrm{Pr}[Y_r=0]\le \frac{2^r}{F_0}.$$ (17)

4 Johnson-Lindenstrauss Lemma

JL Lemma states that we can map data that lie in a high-dimensional space to a low-dimensional one, preserving some of the structures in data.

Lemma 1 (JL Lemma).

Let $S$ be a set of $n$ points in ${ℝ}^d$. For some dimension $k=O(\frac{\ln n}{{ϵ}^2})$, there exists a matrix $A\in {ℝ}^{k\times d}$ such that $\forall u,v,\in S$,

$$(1-ϵ){\Vert u-v\Vert }^2\le {\Vert Au-Av\Vert }^2\le (1+ϵ){\Vert u-v\Vert }^2.$$ (18)

4.1 Norm Preservation

Lemma 2.

For any integer , and integer $k>\frac{4\log \left(\frac{2}{\delta }\right)}{{ϵ}^2-{ϵ}^3}$, there exists a distribution on $k\times d$ real matrices, such that for any $x\in {ℝ}^d$,

$$\mathrm{Pr}\left((1-ϵ){\Vert x\Vert }^2\le {\Vert Ax\Vert }^2\le (1+ϵ){\Vert x\Vert }^2\right)>1-\delta .$$ (19)

Proof of JL Lemma by lemma 2..

Let $\delta =\frac{1}{n^3}$. We apply union bound over $u,v$, and the proof is done. ∎

In fact $A_{ij}\sim 𝒩(0,{\sigma }^2)$ is the construction we need for this lemma.

Proof of lemma 2.

Random choose the entry of $A\in {ℝ}^{k\times d}$. $A_{ij}\sim 𝒩(0,\frac{1}{k})$.

$${(Ax)}_1=\sum _{i=1}^d{A}_{1,i}{x}_i$$ (20)

This is a random variable $𝒩(0,\frac{{\Vert x\Vert }^2}{k})$.

$$𝔼[{\Vert Ax\Vert }^2]=k\cdot 𝔼\Vert {(A{x}_1)}^2\Vert =k\frac{{\Vert x\Vert }^2}{k}={\Vert x\Vert }^2.$$ (21)

Now let $Z_i\sim 𝒩(0,\frac{{\sum }_{i=1}^d{x}_i^2}{k})$

$\mathrm{Pr}\left({\Vert Ax\Vert }^2\ge (1+ϵ){\Vert x\Vert }^2\right)$ $=\mathrm{Pr}\left({\displaystyle \sum _{i=1}^k}{Z}_i^2\ge (1+ϵ){\Vert x\Vert }^2\right)$ (22)

$=\mathrm{Pr}\left({\displaystyle \sum _{i=1}^k}{Y}_i^2\ge (1+ϵ)k\right),\text{where}{Z}_i\sim 𝒩(0,1)$ (23)

$=\mathrm{Pr}\left(\exp \left({\displaystyle \sum _{i=1}^k}{Y}_i^2\right)\ge e^{(1+ϵ)k}\right)$ (24)

$\le {\displaystyle \frac{{\prod }_{i=1}^k𝔼(e^{t{Y}_i^2})}{e^{tk(1+ϵ)}}}$ (25)

$={\displaystyle \frac{1}{{(1-2t)}^{k/2}{e}^{tk(1+ϵ)}}}$ (26)

The last equality holds because $𝔼(e^{t{X}^2})=\frac{1}{\sqrt{1-2t}}$ for . Then applying the fact that $1-x\le e^{-x}\le 1-x+\frac{x^2}{2}$ and let $t=\frac{ϵ}{2(1+ϵ)}$, $k>\frac{4\log \left(2/\delta \right)}{{ϵ}^2-{ϵ}^3}$,

$$\mathrm{Pr}\left({\Vert Ax\Vert }^2\ge (1+ϵ){\Vert x\Vert }^2\right)\le \frac{\delta }{2}.$$ (27)

∎

4.2 Packing

In ${ℝ}^k$ we can only have $k$ perfectly orthogonal vectors. Let $e_1,\mathrm{\dots },e_n\in {ℝ}^n$ be unit orthogonal vectors. After applying JL lemma, we have $e_1^{\prime },\mathrm{\dots },e_n^{\prime }\in {ℝ}^k$. Then $⟨e_i,e_j⟩\le ϵ$ for $i\ne j$.

This means that for $k\ge 1$, , $\exists n=e^{\mathrm{\Omega }({ϵ}^{2}k)}$ near-orthogonal vectors in ${ℝ}^k$.

Lower bound. Let $e_i^{\prime },e_j^{\prime }$ be two $ϵ$-near orthogonal vectors in ${ℝ}^k$, then two unit balls with centers $e_i^{\prime },e_j^{\prime }$ with radius $\frac{1}{2}\sqrt{2-2ϵ}$ are disjoint. However, the total volume of the ball with radius $1+\frac{\sqrt{2-2ϵ}}{2}$ is $O(e^{O(ϵd)})$.

With a more fine-grained analysis, we can get a tighter lower bound $O(e^{\mathrm{\Omega }({ϵ}^{2}d)})$

4.3 Application: Approximate Nearest Neighbor

$x_1,\mathrm{\dots },x_n\in {ℝ}^d$. Given a query $y\in {ℝ}^d$, find the closest $x_i$ to $y$.

If $d$ is small, we have efficient data structures with quasi-linear in space and in $\log n$ time.

If $d$ is large, we need space $O(nd)$ and query $O(nd)$; or $n^{O(d)}$ in space and query time $O(d\log n)$.

Definition 4.1 ($ϵ$-Approximate NN).

Given $y$, an $ϵ$-approximate nearest neighbor is an output $i$ such that $\Vert y-x_i\Vert \le (1+ϵ){\min }_j\Vert y-x_j\Vert$.

Assume the closest point to $y$ has distance 1.

• Preprocess:

  Fix a grid on ${ℝ}^d$ with side length $ϵ/\sqrt{d}$. Let $G_i$ be the set of grid cells that contain at least one point at a distance at most 1 from $x_i$.

  Store $(c,i)$ for each $c\in G_i$.

• The space consumption for each $i$:

  $$\frac{2^d/d^{d/2}}{{(\frac{ϵ}{\sqrt{d}})}^d}\sim {ϵ}^{-d}.$$ (28)

• The query time is $O(d)$.

How to do better using JL lemma?

In the preprocessing phase, project $x_i$ to a space with dimension $d^{\prime }=O(\frac{\log n}{e^2})$.

The space cost is then

$$n^{O(\log \left(1/ϵ\right)/{ϵ}^2)}$$ (29)

Time cost of projection during a query is $d{ϵ}^{-2}\log n$ time, so the time is

$$d{ϵ}^2\log n$$ (30)

5 Linear Programming

Standard form

$\underset{x}{\max }{c}^{T}x$

$\mathrm{s}.\mathrm{t}.$ $Ax\le b,x\ge 0.$ (31)

Dual problem

$\underset{y}{\min }{b}^{T}y$ (32)

$\mathrm{s}.\mathrm{t}.$ $A^{T}y\ge c,y\ge 0.$ (33)

5.1 Uncapacitated Facility Location

Let $D$ be the set of clients and $F$ be a set of facilities. There is a close $f_i$ to open facility $i$.

Goal: choose a subset of $F^{\prime }\subseteq F$ that minimizes ${\sum }_{i\in F^{\prime }}{f}_i+{\sum }_{j\in D}{\min }_{i\in F^{\prime }}{c}_{ij}$.

$c_{ij}$ should satisfy the triangle quality.

We find an equivalent integer programming:

$\underset{x,y}{\min }$ ${\displaystyle \sum _{i\in F}}{f}_i{y}_i+{\displaystyle \sum _{i\in F,j\in D}}{c}_{ij}{x}_{ij}$

$\mathrm{s}.\mathrm{t}.$ ${\displaystyle \sum _{i\in F}}{x}_{ij}=1,\forall j\in D,$

$x_{ij}\le y_i,\forall i,j,$

$x_{ij},y_i\in \{0,1\}.$ (34)

This problem is in general NP-hard. Hence we relax the integer constraint to $x_{ij},y_i\in [0,1]$.

How to round a solution of the linear program to an integer solution?

Fix an order $j_1,\mathrm{\dots },j_k$ for clients. Let $N(j)=\{i:x_{ij}>0\}$. We say $j$ and $j^{\prime }$ are close if $N(j^{\prime })\cap N(j)\ne \mathrm{\varnothing }$.

Dual problem:

$\underset{v}{\max }{\displaystyle \sum _{j\in D}}{v}_j$ (35)

$\mathrm{s}.\mathrm{t}.$ $v_j\le c_{ij}+w_{ij},\forall i\in F,j\in D.$ (36)

${\displaystyle \sum _{j\in D}}{w}_{ij}\le f_i,\forall i\in F$ (37)

$w_{ij}\ge 0.$ (38)

Greedy deterministic LP rounding

• Solve Primal and dual LPs to obtain $x_{ij}^{*}$ and $v_j^{*}$
  

• Order the set $D$ of users, according to increasing $v_j^{*}$.

  For a user in $D$,

• Let $j$ be the user of smallest $v_j^{*}$, Let $i\in N(j)$ minimize $f_i$. Open facility $i$, assign it to user $j$. Remove $j$ from $D$.

• $\forall j^{\prime }D,N_j^{\prime }\cap N_j\ne \mathrm{\varnothing }$, assign $j^{\prime }$ to $i$. Remove $j^{\prime }$ from $D$.

Analysis.

Note that ${\sum }_{i\in N(j_k)}{x}_{i{j}_k^{*}}=1$, we have

${\displaystyle \sum _k}{f}_{i_k}$ $={\displaystyle \sum _k}{f}_{i_k}{\displaystyle \sum _{i\in N(j_k)}}{x}_{i{j}_k}^{*}$ (39)

$\le {\displaystyle \sum _k}{\displaystyle \sum _{i\in N(j_k)}}{f}_i{x}_{i{j}_k}^{*}$ ($f_{i_k}\le f_i,\forall I\in N(j_k)$)

$\le {\displaystyle \sum _k}{\displaystyle \sum _{i\in N(j_k)}}{f}_i{y}_i^{*}$ (LP constraint)

$\le {\displaystyle \sum _i}{f}_i{y}_i^{*}.$ (40)

Suppose a user $\mathrm{\ell }$ is assigned to facility $i_k$. Let $h\in N(l)\cap N(j_k)$.

$c_{i_{k}l}$ $\le c_{i{j}_k}+c_{h{j}_k}+c_{hl}$ (41)

$\le v_{j_k}^{*}+v_{j_k}^{*}+v_l^{*}.$ (42)

$\le 3v_l^{*}.$ (43)

This is because complementary slackness implies

$$\text{if}{x}_{ij}^{*}>0\to v_j^{*}=c_{ij}+w_{ij}\ge c_{ij}.$$ (44)

Therefore,

$$\sum _j{c}_{g(i)j}\le 3\sum _j{v}_j^{*}\le 3Z_{LP}^{*}$$ (45)

$$cost=facility+clientconnection\le \sum _i{f}_i{y}_i^{*}+3Z_{LP}^{*}\le 4Z_{IP}^{*}.$$ (46)

6 Semi-definite programming

We consider the Max-Cut problem on a graph $G=(V,E)$. We want to choose a subset $U\subseteq V$, to maximize $|E(U,V\backslash U)|$, i.e., to maximize the number of edges connecting a node in $U$ to a node outside $U$.

Integer program for Max-Cut

$\underset{(u,v)\in E}{\max }{z}_{uv}$

$\mathrm{s}.\mathrm{t}.$ $z_{uv}\le x_u+x_v$

$z_{uv}\le (1-x_u)+(1-x_v)$

$z_{uv},x_u\in \{0,1\}$ (47)

Randomly cutting the graph gives us a $1/2$ approximation.

$\underset{(u,v)\in E}{\max }{\displaystyle \frac{1-x_u{x}_v}{2}}$ (48)

$s.t.x_i\in -1,1,\forall i\in V,.$ (49)

6.1 SDP definition

Definition 6.1 (Positive semi-definite matrix).

Let $X\in {ℝ}^{n\times n}$ be symmetric. $X$ is positive semi-definite or $X⪰0$, if the following equivalent statements are true:

• $\forall a\in {ℝ}^n$, $a^{T}xa\ge 0$,

• $X=B^{T}B$ for some $B$.

• All eigenvalues of $X$ are nonnegative.

Definition 6.2 (SDP standard form).

$\underset{X\in {ℝ}^{n\times n}}{\min }tr(C^{T}X)$

$\mathrm{s}.\mathrm{t}.$ $tr(A_i^{T}X)=b_i,X⪰0.$ (50)

Dual problem

$\underset{y}{\max }{b}^{T}y$ (51)

${\displaystyle \sum _{i=1}^m}{y}_i{A}_i+S=C$ (52)

$S⪰0$ (53)

To derive this, remember that we want

$$⟨C,X⟩\ge \sum _i{y}_i⟨A_i,X⟩=b^{T}y.$$ (54)

so $⟨C-{\sum }_i{y}_i{A}_i,X⟩\ge 0$ for all $X⪰0$, which means $C-{\sum }_i{y}_i{A}_i⪰0$.

6.2 Strong duality

Theorem 6.3 (Slater’s condition).

Strong duality holds for SDP problems if the feasible region has an interior point.

6.3 Max Cut

Now we relax the max cut problem to a SDP problem.

$\underset{u,v\in E}{\max }1-⟨x_u,x_v⟩$ (55)

$\mathrm{s}.\mathrm{t}.$ $x_i\in {𝕊}^{n-1}.$ (56)

Then let $A$ be the adjacency matrix and $X={\sum }_{ij}{x}_i{x}_j^T$ be the gram matrix. Then this is a SDP.

Theorem 6.4 (This is an SDP!).

Let $A$ be the adjacency matrix, $A_{ij}=1$ if $(i,j)\in E$ and $A_{ij}=0$ otherwise. We define $X$ to be the gram matrix $X_{ij}=x_i^T{x}_j$. Then $MaxCu{t}^{\prime }$ is equivalent to the following SDP

$\min$ $⟨X,A⟩=tr(A^{T}X)$

$\mathrm{s}.\mathrm{t}.$ $X⪰0,X\in {𝕊}_n$

$X_{ii}=1,\forall i.$ (57)

Theorem 6.5 (Goemans-Williamson).

${\alpha }_{gw}={\min }_{0\le \theta \le \pi }\frac{2}{\pi }\frac{\theta }{1-\cos \theta }\sim 0.87856.$

Solve the SDP to obtain $X$. Then $X_{uv}=⟨x_u,x_v⟩$. Find $x_u$ by decomposing $X=U^{T}U$. Choose a vector $a$ uniformly on the sphere ${𝕊}^{n-1}$.

Set $x_u=sign(⟨a,x_u⟩)$.

6.4 Quadratic programs

$$OPT=\underset{x_i,y_i\in \{\pm 1\}}{\max }\sum _{ij}{A}_{ij}{x}_i{y}_j.$$ (58)

This problem is hard. Specifically, it is harder than Max-cut, i.e., ${\max }_{x_i\in \{\pm \}}\frac{1}{2}(1-x_i{x}_j)$. To see this, let $A_{ii}$ be extremely large, so $x_i=y_i$ must hold. Then Max-cut is reduced to this problem.

Relaxtion

$$OP{T}^{\prime }=ma{x}_{\Vert u_i\Vert =1,\Vert v_i\Vert =1}{A}_{ij}⟨u_i,v_j⟩=A_{ij}{z}_{ij}.$$ (59)

Let where $C,D$ has diagonal entries to be 0. Since $B=W{W}^T$, for $W=\left(\begin{array}{c}u\\ v\end{array}\right)$, $B⪰0$.

This is an SDP program.

Theorem 6.6 (Grothendieck’s inequality).

$$OPT\le OP{T}^{\prime }\le \frac{\pi }{2\ln \left(1+\sqrt{2}\right)}OPT.$$ (60)

We first try the hyperplane rounding we used in Goemans-Williamson,

SDP contributes: $A_{ij}⟨u_i,v_j⟩=A_{ij}\cos {\theta }_{ij}$.

Rounding contributes: $A_{ij}\cdot \left(-1\cdot ({\theta }_{ij}/\pi )1\cdot (1-{\theta }_{ij}/\pi )\right)=\frac{2A_{ij}{\theta }_{ij}}{\pi }$

However, $A_{ij}$ could be negative, making this bound infeasible.

Fortunately, we have the following lemma, which directly proves the theorem. To see this, we first apply this transformation in the lemma and then do the hyperplane rounding.

Lemma 3.

For any unit vectors $u_1,\mathrm{\dots },u_m$, $v_1,\mathrm{\dots },v_n$, then there exists a new set of unit vectors $u_1^{\prime },\mathrm{\dots },u_m^{\prime },v_1^{\prime },\mathrm{\dots },v_n^{\prime }$, s.t.

$${𝔼}_a[sign(a^T{u}_i^{\prime })sign(a^T{v}_j^{\prime })]=\frac{2}{\pi }\ln \left(1+\sqrt{2}\right)⟨u_i,v_j⟩.$$ (61)

Proof.

Define tensor product $U^{\otimes 2}=[u_1^2,u_1{u}_2,\mathrm{\dots },u_n^2]$. Let $c={\sinh }^{-1}1=\ln \left(1+\sqrt{2}\right)$.

By Taylor’s expansion,

$$\sin c⟨u,v⟩=\sum _{k=0}^{\mathrm{\infty }}{(-1)}^k\frac{c^{2k+1]}}{(2k+1)!}{⟨u,v⟩}^{2k+1}$$ (62)

∎

Let

$$u^{\prime }=[\sqrt{u},(-1)\sqrt{\frac{c^3}{3!}}{u}^{\otimes 3},\mathrm{\dots },{(-1)}^k\sqrt{\frac{c^{2k+1}}{(2k+1)!}}{u}^{\otimes 2k+1}]$$ (63)

and

$$v^{\prime }=[\sqrt{v},\sqrt{\frac{c^3}{3!}}{v}^{\otimes }3,\mathrm{\dots },\sqrt{\frac{c^{2k+1}}{(2k+1)!}}{v}^{\otimes 2k+1}]$$ (64)

Then $⟨u^{\prime },v^{\prime }=\sin \left(c⟨u,v⟩\right)$.

And $⟨u^{\prime },u^{\prime }=\sinh (c)=1$. This is because removing the sign in the Taylor’s expansion yields $\sinh (c⟨u,v⟩)$.

Then

$${𝔼}_a[sign(a^{T}u)sign(a^{T}v)]=\frac{2}{\pi }\arcsin ⟨u^{\prime },v^{\prime }⟩=\frac{2}{\pi }c⟨u,v⟩$$ (65)

Lavasz theta function

Let $\alpha (G)$ be the size of the largest independent set of $G$.

Let $\chi (G)$ be the chromatic number of $G$. And let $\overline{G}$ be the complement of $G$.

Then

$$\chi (\overline{G})\ge \alpha (G).$$ (66)

We define

$\theta (G)$ $:=\min k,$ (67)

$\mathrm{s}.\mathrm{t}.$ $⟨v_i,v_j⟩=-{\displaystyle \frac{1}{k-1}}\forall (i,j)\notin E,$ (68)

$⟨v_i,v_i⟩=1.$ (69)

Theorem 6.7.

$\alpha (G)\le \theta (G)\le \chi (\overline{G})$.

Proof.

First $\theta (G)\le \chi (\overline{G})$.

Fact: $\exists k$ unit vectors $u_1,\dot{,}{u}_k$ such that $⟨u_i,u_j⟩=-\frac{1}{k-1}$.

Then any $k$-coloring of $\overline{G}$ yields $u_1,\mathrm{\dots },u_k$.

The other direction: $\theta (G)\ge \alpha (G)$. We solve the SDP to obtain $v_i$. For an independent set, consider $v_1,\mathrm{\dots },v_s$ of the independent set

$$0\le (\sum _{i=1}^s{v}_i^T)(\sum _{i=1}^s{v}_i)\le \sum _{i=1}^s{v}_i^T{v}_i+\sum _{i\ne j}{v}_i^T{v}_j$$ (70)

Then at least one term of $v_i^T{v}_j\ge -\frac{s}{2}\left(\genfrac{}{}{0pt}{}{s}{2}\right)=-\frac{1}{s-1}$. However, $⟨v_i,v_j⟩=-\frac{1}{\theta (G)-1}$. ∎

7 Online Algorithms

7.1 Multiplicative Weights

We wish to make predictions over $T$ days, relying on $n$ expects that we have. Define $f_i^t$ to be the loss of expert $i$, on day $t$. Without loss of generality, $\parallel f^t\parallel )\mathrm{\infty }\le 1$.

Our goal is to minimize the regret

$$Regret=\sum _{t=1}^T⟨p^t,f^t⟩-\underset{u}{\min }\sum _{t=1}^T{f}_i^t.$$ (71)

Naive idea: to pick the best expert so far. Then there exists a set of $f^{(t)}$ so that the regret $\sim T(1-\frac{1}{n})$.

Weighted Majority. Assuming we are making binary choices. Assign each expect $i$ with weight $w_i^{(1)}=1$. We can make a majority vote and predict

$$x=\frac{{\sum }_{i=1}^n{w}_i{x}_i}{{\sum }_{i=1}^n{w}_i}.$$ (72)

Assumption: There is an expert who is always correct.

Algorithm: Remove the experts with the wrong predictions. Then each time we make a mistake, we halve the number of experts. Regret = $O(\log n)$. This is basically the idea of the multiplicative weights algorithm.

If we remove the assumption that there is an expert always correct, we can restart after removing all experts. The bound is $O((M+1)\log n)$ if the best expert makes $M$ mistakes.

The idea of multiplicative weight on binary outcomes

• Set $w_i^{(1)}=1$.

• After observing the outcome at day $t$, set $w_i^{(t+1)}=\frac{w_i^{(t)}}{2}$ if $i$ makes a wrong prediction.

Analysis: let ${\mathrm{\Phi }}^{(t)}={\sum }_{i=1}^n{w}_i^{(t)}$. Then

$${\mathrm{\Phi }}^{(T+1)}\ge {(\frac{1}{2})}^{\mathrm{\#}{i}^{\prime }s\text{mistakes}}$$ (73)

$${\mathrm{\Phi }}^{(t+1)}\le \frac{3}{4}{\mathrm{\Phi }}^{(t)},\text{(when the algorithm makes a mistake)}$$ (74)

Therefore,

$$\mathrm{\#}\text{mistakes}\le \frac{1}{\log 4/3}(\mathrm{\#}{i}^{\prime }s\text{mistakes}+\log n)$$ (75)

However, this does not guarantee a bound on the regret, due to the $\log 4/3$ constant. We now state the full version of multiplicative weights.

Multiplicative weights algorithm

• Set $w_i^{(1)}=1$.

• For $t=1,\mathrm{\dots },T$,

  • Follow expert $i$ with probability $p_i^t=\frac{w_i^t}{{\sum }_i{w}_i^t}$.

  • $w_i^{(t+1)}\leftarrow w_i^{(t)}(1-ϵf_i^t),\forall i.$

Theorem 7.1.

If , then the multiplicative weight gives the following bound on regret

$$regret\le \frac{\log n}{ϵ}+ϵT.$$ (76)

If $T$ is known, $ϵ=\sqrt{\frac{\log n}{T}}$, regret $\le 2\sqrt{T\log n}$.

Proof.

Define a potential function ${\mathrm{\Phi }}^t={\sum }_i{w}_i^{(t)}$. Then

$${\mathrm{\Phi }}^{(t+1)}=\sum _i{w}_i^{(t)}(1-ϵf_i^t)=\sum _i{p}_i^t{\mathrm{\Phi }}^t(1-ϵf_i^t).$$ (77)

Therefore,

$$𝔼{\mathrm{\Phi }}^{(t+1)}=𝔼{\mathrm{\Phi }}^{(t)}(1-ϵ𝔼{\mathrm{\ell }}_t)\le {\mathrm{\Phi }}^t\exp \left(-ϵ𝔼{\mathrm{\ell }}_t\right).$$ (78)

Hence $𝔼{\mathrm{\Phi }}^{(T)}\le n\exp \left(-ϵ𝔼L_{1:t}\right)$.

On the other hand, let $i$ be any expert,

$$𝔼{\mathrm{\Phi }}^{(T)}\ge w_i^T\ge \prod _{t=1}^T\exp \left(-ϵf_i^t-{ϵ}^2{(f_i^t)}^2\right).$$ (79)

Then let $i$ be the optimal expert,

$$𝔼[L_{1:t}]-OPT\le \frac{1}{ϵ}(\log n+{ϵ}^2\sum _{t=1}^T{(f_i^t)}^2)\le \frac{\log n}{ϵ}+ϵT.$$ (80)

∎

Remark. When ${\Vert f^t\Vert }_{\mathrm{\infty }}\le \rho$, regret $\le \frac{{\rho }^2\log n}{ϵ}+ϵT$.

7.2 Application of Multiplicative Weight

Zero-sum Games.

$$v=\underset{x}{\min }\underset{y}{\max }c(x,y)$$ (81)

Theorem 7.2 (Von Neumann).

Let $x,y$ be mixed strategies of players $A$ and $B$, then

$$\underset{x}{\min }\underset{y}{\max }c(x,y)=\underset{y}{\max }\underset{x}{\min }c(x,y).$$ (82)

Another way of phrasing: $\exists (x,y),x,y\ge 0,{\sum }_i{x}_i={\sum }_i{y}_i=1$, then there is a value $v$,

$$x^{T}M\ge v,My\le v,where{M}_{ij}=c(i,j).$$ (83)

We try to prove this theorem by multiplicative weights. Let $(p^1,q^1),\mathrm{\dots },(p^T,q^T)$ be the strategies over $T$ days.

Then

$$-(\sum _{t=1}^T⟨p^t,A{q}^t⟩-\underset{i}{\max }\underset{t=1}{\overset{T}{\sum }}{(A{q}^t)}_i)\le \frac{\ln m}{ϵ}+ϵT$$ (84)

and

$$\sum _{t=1}^T⟨q^t,A{p}^t⟩-\underset{i}{\max }\sum _{t=1}^T{(A{p}^t)}_i\le \frac{\ln m}{ϵ}+ϵT$$ (85)

Adding them together,

$$\underset{i}{\max }\sum _{t=1}^T{(A{q}^t)}_i-\underset{j}{\min }\sum _{t=1}^T{(p_{}^t{}_{}{}^{T}A)}_j\le \frac{2\ln m}{ϵ}+2ϵT=2\sqrt{\frac{logn}{T}}.$$ (86)

Let $\overline{P}=\frac{1}{T}{\sum }_{i=1}^T{p}^t,\overline{q}=\frac{1}{T}{\sum }_{i=1}^T{q}^t$, then

$$\underset{i}{\max }{(A\overline{q})}_i-\underset{j}{\min }({\overline{q}}^{T}A)\le \delta =2\sqrt{\frac{\log n}{T}}.$$ (87)

This means

$$\underset{j}{\min }{({\overline{p}}^{T}A)}_j\le {\overline{P}}^{T}A\overline{q}\le \underset{i}{\max }{(A\overline{q})}_i\le \underset{j}{\min }{({\overline{p}}^{t}A)}_j+\delta$$ (88)

When $T$ goes to infinity, the two bounds are equal, which proves our theorem.

7.3 Application: Max Flow

Consider an unweighted graph $G=(V,E)$. The max flow problem can described by a linear program:

Let $P_{s,t}$ be the set of all paths from $s$ to $t$, then

$\underset{p\in P_{s,t}}{\max }x(p).$ (89)

$\mathrm{s}.\mathrm{t}.$ ${\displaystyle \sum _{p:e\in p}}x(p)\le 1,\forall e$ (90)

$x(p)\ge 0.$ (91)

The dual problem:

$\underset{e}{\min }{\displaystyle \sum _e}\mathrm{\ell }(e)$ (92)

$\mathrm{s}.\mathrm{t}$ ${\displaystyle \sum _{e\in p}}\mathrm{\ell }(e)\ge 1,\forall p\in P_{s,t}$ (93)

$\mathrm{\ell }(e)\ge 0.$ (94)

Zero sum game conversion:

Let $\gamma$ be the optimal flow, a player $P$ chooses a path, and a player $D$ chooses an edge (might be a mixed strategy). Payoff for $D$ is 1 if $e\in P$ and 0 otherwise.

Lemma 4.

Let $v$ be the value of the game. Then $v=\frac{1}{\gamma }$.

Proof.

Given an optimal solution $\mathrm{\ell }(e)$ to the dual, $D$ plays edge $e$ with probability $\frac{\mathrm{\ell }(e)}{{\sum }_e\mathrm{\ell }(e)}=\frac{\mathrm{\ell }(e)}{\gamma }$, then for all paths, the payoff for $D$ is

$$\sum _{e\in P}\frac{\mathrm{\ell }(e)}{\gamma }=\frac{1}{\gamma }\sum _{e\in P}\mathrm{\ell }(e)\ge \frac{1}{\gamma }.$$ (95)

Let $x(p)$ be the optimal solution to the primal problem. $P$ chooses a path $p$ with probability $\frac{x(p)}{\gamma }$. For any edge,

$$\mathrm{Pr}[e\in p]=\sum _{p:e\in p}=\frac{1}{\gamma }\sum _{p:e\in p}x(p)\le \frac{1}{\gamma }.$$ (96)

∎

Remark. We now want to run a multiplicative weights algorithm on this zero-sum game, but the problem is that the primal problem has exponentially many variables. We have make some modification to fix this issue.

• For each $t=1,\mathrm{\dots },T$, use multiplicative weights to choose a distribution $w_t$ on edges. Let $P^t$ be the best response to $w_t$, which is to find the shortest path algorithm with weights $w_t$.

• Set the reward vector to be: $r^t(e)=\mathrm{𝟙}[e\in P^t]$.

• Suppose the solution is $p_1,\mathrm{\dots },p_t$, we route $\frac{\gamma }{T}$ units of flow on each $p^i$. Denote this route as $f$.

Lemma 5.

This algorithm routes $\le 1+\delta$ units on each edge, for $T=\frac{4{\gamma }^2\ln m}{{\delta }^2}$.

Proof.

Suppose for contradiction that $\exists e\in f$ routes more than $(1+\delta )$ on $e$, then there is more than $\frac{(1+\delta )T}{\gamma }$ of the path $p^1,\mathrm{\dots },p^T$ use edge $e$.

If the $D$ player players edge $e$ in hindsight, then the payoff is more than $\frac{(1+\delta )}{\gamma }$.

In each step, player $D$ gets at most $\frac{1}{\gamma }$ in expectation, because $P^t$ is the best response.

Note that $\frac{\delta }{\gamma }\le \frac{Regret}{T}\le \frac{2\sqrt{T\log n}}{T}$. ∎

7.4 Application: Adaboost

Goal: to learn an unknown function $X\to \{0,1\}$, given a sequence of training samples $(x,c(x))$, $x\sim D$. We want to minimize

$${𝔼}_{x\sim D}[|h(x)-c(x)|].$$ (97)

Weak learner: does slightly better than randomly guessing, with loss $\frac{1}{2}-\gamma$.

We consider samples in the training set as experts.

For hypothesis $h$, the penalty for expert $x$ is 0 if $h(x)\ne c(x)$ and 1 otherwise. (Intuition: we want to sample more on hard samples).

In each round, the algorithm gives a distribution $D^t$ over experts and obtains a hypothesis $h^t$ which is a weak learner for $D^t$, i.e., the penalty $M(D^t,h^t)\ge \frac{1}{2}+\gamma$.

The final hypothesis $h_{final}$ labels $x$ according to a majority vote over $h^1(x),\mathrm{\dots },h^T(x)$.

Analtsis:

Let $S$ be the set of training samples labeled incorrectly by the final hypothesis.

Penalty for each $x\in S$, then since $h_{final}(x)$ is a majority vote,

$$\sum _{t}M(x,h^t)\le \frac{T}{2}.$$ (98)

Let the potential function be defined by ${\mathrm{\Phi }}^t={\sum }_x{w}_t$.

Then

$${\mathrm{\Phi }}^T\le {\mathrm{\Phi }}^1{e}^{-\alpha {\sum }_{t}M(D^t,h^t)}\le n{e}^{0\alpha T(\frac{1}{2}+\gamma )}$$ (99)

$${\mathrm{\Phi }}^T\ge \sum _{x\in S}{w}_x\ge \sum _{x\in S}(1-\alpha )\sum _{t}M(x,h^t)\ge |S|{(1-\alpha )}^{T/2}$$ (100)

Then we derive $T=\frac{2}{{\gamma }^2}\log \left(\frac{1}{{ϵ}^{\prime }}\right)$, where ${ϵ}^{\prime }=\frac{|S|}{n}$

8 Spectral Method

8.1 Sparsest cut

Definition 8.1 (Edge expansion).

Let $G=(V,E)$ be an undirected graph, and $S\subseteq V$ be a subset of vertices. The edge expansion of $S$ is

$$\varphi (S)=\frac{E(S,V-S)}{d(S)}$$ (101)

where $d(S)={\sum }_{v\in S}d(v)$ be the total degree of the vertices in $S$.

The edge expansion of a cut $(S,V-S)$ is $\max \{\varphi (S),\varphi (V-S)\}$.

The edge expansion of a graph is

(102)

Sparsest cut: Compute $\varphi (G)$.

Example.

• Cycle: $2/n$

• Clique: $1/2$.

• Barbell: $1/n^2$

Let $A$ be the adjacency matrix of $G$. Suppose $G$ is a $d$-regular graph. The normalized Laplacian is defined as

$$L=I-\frac{1}{d}A.$$ (103)

We compute the eigenvalues ${\lambda }_1\le {\lambda }_2\le \mathrm{\cdots }\le {\lambda }_n$, then the Cheeger inequality states that

$$\frac{\lambda }{2}\le \varphi (G)\le \sqrt{2{\lambda }_2}.$$ (104)

Lemma 6.

Let $M\in {ℝ}^{n\times n}$ be a symmetric matrix and ${\lambda }_1\le \mathrm{\cdots }\le {\lambda }_n$ be eigenvalues of $M$. Then

$${\lambda }_k=\underset{k-dimV}{\min }\underset{x\in V-\{0\}}{\max }\frac{x^{T}Mx}{x^{T}x}.$$ (105)

Fact. If $x_1$ is an eigenvector of ${\lambda }_1$, then

$${\lambda }_2=\underset{x\ne 0,x⟂x_1}{\max }\frac{x^{T}Mx}{x^{T}x}$$ (106)

Note that the Laplacian of a $d$-regular matrix is $L=dI-A$.

$$x^{T}Lx=\sum _{(u,v)\in E}{(x_u-x_v)}^2.$$ (107)

Let $\overline{L}=L/d$.

Theorem 8.2.

Let $G$ be a $d$-regular, undirected graph, let ${\lambda }_1\le \mathrm{\cdots }\le {\lambda }_n$ be the eigenvalues of $\overline{L}$. Then

• ${\lambda }_1=0$ and ${\lambda }_n\le 2$.

• ${\lambda }_k=0$ if and only if $G$ has at least $k$ connected components.

• ${\lambda }_n=2$ if and only if at least one of the connected components of $G$ is bipartite.

Proof.

i. Trivial.

ii. ${\lambda }_k={\min }_{k-dimS}{\max }_{x\in S-\{0\}}\frac{{\sum }_{(u,v)\in E}{(x_u-x_v)}^2}{d{\sum }_v{x}_v^2}.$ If ${\lambda }_k=0$.

If ${\lambda }_k=0$, there exists a $k$-dimensional $S$, $\forall x\in S$, $x_u=x_v$ for all $(u,v)\in E$. This means $x$ must be constant within each connected component. Therefore, the dimension of $S$ can be at most the number of connected components. The reverse direction can be proved by letting $S$ be the space of vectors that are constant within each connected component.

iii. ${\lambda }_n={\max }_{x\ne 0}\frac{x^T\overline{L}X}{x^{T}x}$. Note that

$$2x^{T}x-x^T\overline{L}x=\frac{1}{d}\sum _{(u,v)\in E}{(x_u+x_v)}^2.$$ (108)

Therefore,

$${\lambda }_n=2-\underset{x\ne 0}{\min }\frac{{\sum }_{(u,v)\in E}{(x_u+x_v)}^2}{d{\sum }_v{x}_v^2}.$$ (109)

If ${\lambda }_n=2$, then there is a vector $x\ne 0$, with ${\sum }_{(u,v)\in E}{(x_u+x_v)}^2$, so for all $(u,v)\in E$, $x_u=-x_v$. Let , $B=\{u:x_u>0\}$. Then $A\cup B$ must be disconnected from $\{v:x_v=0\}$. Moreover, $A\cup B$ is bipartite. ∎

8.1.1 Generalize to general graphs

$L=D-A$ where $D=diag(d_1,\mathrm{\dots },d_n)$. $\overline{L}=I-D^{-1/2}A{D}^{-1/2}$.

Then we generalize

$$\frac{{\sum }_{(u,v)\in E}{(x_u-x_v)}^2}{d}\to \sum _{(u,v)\in E}{\left(\frac{x_u}{\sqrt{d_u}}-\frac{x_v}{\sqrt{d_v}}\right)}^2.$$ (110)

8.1.2 Proof of Cheeger’s theorem

We want to prove $\frac{{\lambda }_2}{2}\le \varphi (G)\le \sqrt{2{\lambda }_2}$.

The easy part: $\frac{{\lambda }_2}{2}\le \varphi (G)$.

Note that ${\lambda }_2$ (To fill.)

The hard part: $\varphi (G)\le \sqrt{2{\lambda }_2}$.

Lemma 7.

Given any $y\in {ℝ}^v$, there exists an algorithm to find $S\subseteq supp(y)$ with

$$\varphi (S)\le \sqrt{2\frac{y^{T}Ly}{y^{T}Dy}}.$$ (111)

Proof.

We can solve the ${\min }_{D^{1/2}y⟂v_1}\frac{y^{T}Ly}{y^{T}Dy}$ problem efficiently when $y\in [-1,1]$. The problem is how should we round the solution.

Algorithm: sweep cut. Choose a threshold $t\in [0,1]$ at random, and output $S_{+}=\{i\in V|y_i^2>t\}$. This procedure can be simply derandomized by enumerating all $n-1$ possible cuts.

${𝔼}_t|E(S_t,{\overline{S}}_t)|$ $={\displaystyle \sum _{(i,j)\in E}}\mathrm{Pr}[(i,j)\text{cut by}{S}_t]$ (112)

$={\displaystyle \sum _{(i,j)\in E}}|y_i-y_j|(y_i+y_j)$ (113)

$\le \sqrt{{\displaystyle \sum _{(i,j)\in E}}{(y_i-y_j)}^2}\cdot \sqrt{{\displaystyle \sum _{(i,j)\in E}}{(y_i+y_j)}^2}$ (114)

$\le \sqrt{{\displaystyle \sum _{(i,j)\in E}}{(y_i-y_j)}^2}\cdot \sqrt{2{\displaystyle \sum _{i\in V}}d(i)y_i^2}$ (115)

The first term is just the numerator. Note that ${𝔼}_t[d(S_t)]={\sum }_{i\in V}d(i){𝔼}_t[\mathrm{𝟙}(i\in S_t)]={\sum }_{i\in V}d(i)y_i^2$.

Therefore,

$$\frac{{𝔼}_t[|E(S_t,{\overline{S}}_t)|]}{{𝔼}_t[d(S_t)]}\le \sqrt{2\frac{y^{T}Ly}{y^{T}Dy}}.$$ (116)

This means

$${𝔼}_t[|E(S_t,{\overline{S}}_t)|-\sqrt{2\frac{y^{T}Ly}{y^{T}Dy}}|d(S_t)|]\le 0.$$ (117)

It means there exists a $t^{*}$ such that

$$\frac{|E(S_{t^{*}},{\overline{S}}_{t^{*}})|}{[d(S_{t^{*}})]}\le \sqrt{2\frac{y^{T}Ly}{y^{T}Dy}}.$$ (118)

∎

Now we only need to show a construction of $z$ from $y$, which satisfies $R(z)\le R(y)$, and at the same time

$$\sum _{i:z_i\ge 0}d(i)\le \frac{d(V)}{2}.$$ (119)

Since $D^{1/2}y⟂v_1$ we know ${\sum }_{i}d(u)y_i=0$. Suppose $y_1\le y_2\le \mathrm{\dots }{y}_n$ WLOG. Find the smallest $j$ such that

$$\sum _{1\le i\le j}d(i)\ge \frac{d(V)}{2}.$$ (120)

and let $z=y-y_j$. Let $z^{+}=\max (0,z)$ and $z^{-}=\min (0,z)$. Then we know

$$\sum _{i:z_i^{-}\ne 0}d(i)\le \frac{d(V)}{2}\text{and}\sum _{i:z_i^{+}\ne 0}d(i)\le \frac{d(V)}{2}$$ (121)

Lemma 8.

$\min \{R(z^{-}),R(z^{+})\}\le R(z)\le R(y)$.

Proof.

First, $R(z)\le R(y)$ because their numerators $\sum {(z_i-z_j)}^2=\sum {(y_i-y_j)}^2$ and their denominators ${\sum }_{i}d(i)z_i^2={\sum }_{i}d(i)y_i^2+{\sum }_{i}d(i)y_j^2-2y_i{\sum }_i{y}_{i}d(i)={\sum }_{i}d(i)y_i^2+{\sum }_{i}d(i)y_j^2\ge {\sum }_{i}d(i)y_i^2$. Note that ${\sum }_i{y}_{i}d(i)=0$ is derived from $D^{1/2}y⟂v_1$.

Moreover,

$$z^{T}Dz=z_{}^{+}{}_{}{}^{T}D{z}^{+}+z_{}^{-}{}_{}{}^{T}D{z}^{-}$$ (122)

and

$$z^{T}Lz\ge z_{}^{+}{}_{}{}^{T}L{z}^{+}+z_{}^{-}{}_{}{}^{T}L{z}^{-}$$ (123)

Then

$$\frac{z_{}^{+}{}_{}{}^{T}L{z}^{+}+z_{}^{-}{}_{}{}^{T}L{z}^{-}}{z_{}^{+}{}_{}{}^{T}D{z}^{+}+z_{}^{-}{}_{}{}^{T}D{z}^{-}}\le R(z).$$ (124)

which means one of $R(z^{-})$ and $R(z^{+})$ must be less than $R(z)$. ∎

Finally, we conclude that $\varphi (G)\le \sqrt{2{\lambda }_2}$ since

$$\varphi (G)=\underset{S:d(S)\le \frac{d(V)}{2},|S|\ne 0}{\min }\varphi (S).$$ (125)

8.2 Spectal Clustering

Problem: input a set of points $a_i$ with a measure of similarity $w_{ij}\ge 0$. How do we cluster them?

• Embed into ${ℝ}^d$ by using eigenvectors of $\overline{L}$. Suppose $(v_1,\mathrm{\dots },v_{d+1})$ are the $d$ smallest eigenvalues. We map $a_i$ to $({(v_2)}_i,\mathrm{\dots },{(v_{d+1})}_i)$.

• When $d=2$, it is equivalent to our sweep cut algorithm.

9 Random Walk

2-SAT problem.

Start with a random assignment. At each step, choose a clause that is not satisfied, and flip a variable in the clause.

Analysis.

Consider the Hamming distance $r\in [0,n]$ between the current assignment to the best. ($n$ is the number of variables). The hitting time to $r=0$ should be $O(n^2)$.

9.1 Random walk on graphs

Let $G=(V,E)$ be an undirected graph.

At each time, a random walk is at some node $i\in V$. At time $t+1$, the random walk chooses a neighbor of $i$ at random and moves to that neighbor.

A “lazy” random walk: stays at $i$ with probability $1/2$.

Stationary distribution.

• Does there exist one?

• If exists, how long does it take to converge? (mixing time)

Let $p^{(t)}$ be the probability distribution at time $t$.

$$p_{t+1}(i)=\sum _{j:(i,j)\in E}{p}_t(j)\frac{1}{d(j)}.$$ (126)

We can write this as a matrix multiplication:

$$p_{t+1}=A{D}^{-1}{p}_t,$$ (127)

where $D=\mathrm{diag}(d_1,\mathrm{\dots },d_n)$, and $A$ is the adjacency matrix. $A{D}^{-1}$ is called the transition matrix.

Definition 9.1 (Stationary distribution).

A probability distribution $\pi$ over $V$ is a stationary distribution if

$$\pi =(A{D}^{-1})\pi .$$ (128)

We can directly write out a stationary distribution

$$\pi =\frac{(d_1,\mathrm{\dots },d_n)}{2m},\text{where}m=|E|.$$ (129)

Definition 9.2 (ergodic).

A random walk is called ergodic if there is a distribution $\pi$, such that for any initial distribution $p_0$,

$$\underset{t\to \mathrm{\infty }}{lim}{p}_t=\pi .$$ (130)

Theorem 9.3.

A random walk is ergodic if and only if it is connected and not bipartite.

Lazy random walk:

$$p_{t+1}(i)=\frac{1}{2}{p}_t(i)+\frac{1}{2}\sum _{(i,j)\in E}\frac{p_t(j)}{d(j)}.$$ (131)

and in matrix forms:

$$p_{t+1}=(\frac{1}{2}I+\frac{1}{2}A{D}^{-1})p_t.$$ (132)

Theorem 9.4.

A lazy random walk is ergodic if and only if $G$ is connected.

Proof of theorem 9.3 and 9.4 for $d$-regular graphs..

Let ${\alpha }_1\ge \mathrm{\cdots }\ge {\alpha }_n$ be the eigenvalues of $\overline{A}=A{D}^{-1}$, and $x_1,\mathrm{\dots },x_n$ be the corresponding eigenvectors.

From theorem 8.2,

• ${\alpha }_1=1,x_1=1/\sqrt{n}$

• if $G$ is connected.

• ${\alpha }_n\ge -1$. If $G$ is not bipartite if and only if ${\alpha }_n>-1$.

Let $p_0={\sum }_{i=1}^n{c}_i{x}_i$, where $c_i=⟨x_i,p_0⟩$. Then

$$p_t=\sum _{i=1}^t{c}_i{\alpha }_i^t{x}_i.$$ (133)

If $G$ is connected and not bipartite, then , for all $i\ne 1$. Thus, ${\alpha }_i^t\to 0$ as $t\to \mathrm{\infty }$.

$$\underset{t\to \mathrm{\infty }}{lim}\underset{i=1}{\overset{n}{\sum }}{c}_i{\alpha }_i^t{x}_i=c_1{x}_1=\frac{\mathrm{𝟏}}{n}.$$ (134)

For lazy random graph, $w_i=\frac{1}{2}(1+{\alpha }_i)\in [0,1)$ when $G$ is connected. So $w_i^t\to 0$ as $t\to \mathrm{\infty }$. ∎

9.2 Mixing time

Definition 9.5 (Mixing time).

The smallest time $t$ such that $D_{TV}(p_t,\pi )\le 1/4$, where $\pi$ is the stationary distribution.

Definition 9.6 (Spectral gap).

We define the spectral gap of a graph by

$$\alpha =\min \{1-{\alpha }_2,1-|{\alpha }_n|\}.$$ (135)

For regular random walks,

$$p_t=\sum _{i=1}^n{c}_i{\alpha }_i^t{x}_i=\frac{1}{n}+\sum _{i=2}^n{c}_i{\alpha }_i^t{x}_i.$$ (136)

Then

$D_{TV}(p_t,\pi )$ $={\Vert {\displaystyle \sum _{i=2}^n}{c}_i{\alpha }_i^t{x}_i\Vert }_1$ (137)

$\le \sqrt{n}{\Vert {\displaystyle \sum _{i=2}^n}{c}_i{\alpha }_i^t{x}_i\Vert }_2$ (138)

$\le \sqrt{n}(1-{\alpha }^t){({\displaystyle \sum _{i=2}^n}{c}_i^2)}^{1/2}\le \sqrt{n}(1-{\alpha }^t).$ (139)

10 Expander Graph

Definition 10.1.

A two-sided spectral expander $(d,\gamma )$ is a graph, such that

• $G$ is d-regular

• $\forall i\ge 2|{\lambda }_i(\overline{L})-1|\le \gamma$

• Explicit: If it takes $poly(n)$ time to produce $A$.

• Strongly explicit: If it takes time $\log n$ to produce the neighbor of a given vertex.

Remark. For complete graphs, ${\lambda }_2(\overline{L})=1/2$. For a path, ${\lambda }_2(\overline{L})=1/n^2$.

Proposition 10.2 (Expanders are reliable networks.).

For expander graphs, if $k$ edges are removed, the largest connected component is $\sim n-\frac{k}{d\varphi }$.

10.1 Random walks on expander graphs

On a complete graph, it takes $O(k\log n)$ bits to represent a $k$-steps random walk. On an expander, it takes $\log n+kd=\log n+O(k)$.

10.2 Application: Pseudo-random number generation

Syooise we are given an algorithm with a constant error rate. We can decrease its error rate to exponentially small by repeating polynomial times.

Using Chernoff bound and repeat $t$ times, the error rate is $C^{-t}$. Suppose the algorithm requires $r$ random bits. The repeat-Chernoff requires $rt$ random bits. However, with expanders, we reduce the number of random bits to $r+10t$.

Algorithm.

• Choose $v\in {\{0,1\}}^r$ at random.

• Take $t-1$ steps running a random walk on $(V={\{0,1\}}^r,E)$ to generate $v_2,\mathrm{\dots },v_t$.

Note that a strongly explicit graph is required, as the number of vertices is exponentially large.

Expander graph on $V$, $d=400$, $\forall i\ge 2$, $\frac{|{\mu }_i||}{d}\le \frac{1}{10}.$ (${\mu }_i$ is the adjacency).

Let $|X|\subseteq {\{0,1\}}^r$ be the set that the algorithm is incorrect on. $|X|\le \frac{2^r}{100}$. Let $S=\{i:v_i\in X\}$. Let $Y=V-X$.

$p_0=\frac{1}{n}$. The characteristic vectors of $X$ and $Y$ is defined ${\chi }_x$ and ${\chi }_y$.

Let $D_x=\mathrm{diag}({\chi }_x)$ and $D_y=\mathrm{diag}({\chi }_y)$. $W=\frac{A}{d}$ is the transition matrix. The probability that a vertex chosen according to $p$ in $X$ is

$${\chi }_x^{T}p=1^T{D}_{x}p.$$ (140)

$q=W{D}_x{p}_0$ is the probability that a walk starts at a vertex in $X$ and goes to $q$. The probability that the walk is in $X$ at time $i\in R$ is ($R$ is an arbitrary subset of time in $1,\mathrm{\dots },t$) We want to show

$$1^T{D}_{Z_t}W{D}_{Z_{t-1}}W\mathrm{\dots }{D}_{Z_1}W{D}_{Z_0}{p}_0\le {\frac{1}{5}}^{|}R|.$$ (141)

where $Z_i=X$ is $i\in R$ and $Y$ otherwise.

Lemma: $\Vert D_{X}W\Vert \le 1/5$.

Then

$$1^T{D}_{Z_t}W{D}_{Z_{t-1}}W\mathrm{\dots }{D}_{Z_2}W{D}_{Z_0}{p}_0=1^T(D_{Z_t}W)(D_{Z_{t-1}}W)\mathrm{\dots }(D_{Z_1}W)(D_{Z_0}W)p_0\le {(1/5)}^R\Vert p_0\Vert$$ (142)

Then,

$$\mathrm{Pr}[|S|>\frac{t}{2}]\le \sum _{|R|>\frac{t}{2}}\mathrm{Pr}[\text{walks is in }X\text{ at times}R]\le {(2/\sqrt{5})}^{t+1}$$ (143)

For lemma: Let $v=c_1\mathrm{𝟏}+y$, with $1^{T}y=0$. Then $\Vert v\Vert \ge \max \{c_1\sqrt{n},\Vert y\Vert \}$.

$$\frac{\Vert D_{x}Wv\Vert }{\Vert v\Vert }$$ (144)

11 Hardness Assumption

11.1 Encryption

Alice sends a message $b$ to Bob. Bob should be the only person who can decode the message.

Private-key encryption

• Shared key: random bit $c\in \{0,1\}$.

• To send a message $b$, Alice sends $b\oplus c$. (One time pad).

Public-Key encryption

• Key generation: Generate a public key and a secret key. Publish $pk$.

• Encryption: take randomness $r$, $Enc(b,pk,r)=c$

• Decryption: $Dec(pk,sk,c)=b$.

Definition 11.1 (Computationally indistinguishable).

We say $(pk,Enc(pk,r,0))\sim (pk,Enc(pk,r,1))$ computationally indistinguishable, if:

If there exists an efficient algorithm that distinguishes $Enc(0),Enc(1)$, then some underlying hardness assumption is broken.

11.2 Hardness

Definition 11.2 (Learning with errors).

The LWE problems are defined by

• $A\in {\mathbb{Z}}_q^{m\times n}$ with $m\gg n\log q$.

• $A$ is sampled uniformly at random,

• Consider $s\in {\mathbb{Z}}_q^n$. Given $As$, solving $s$ is easy.

• Given $As+e$, $e\in {\mathbb{Z}}_q^m$ and $e=O(\sqrt{n})$.

Assumption 11.3 (Decisional LWE assumption).

Let $e$ sampled from a truncated Gaussian, $|e|\le \sigma$ and $\sigma \ge 2\sqrt{n}$.

$$(A,As+e)\sim (A,Unif({\mathbb{Z}}_q^m))$$ (145)

11.3 Encryption scheme from LWE.

Private-key scheme:

• Shared key $s\in {\mathbb{Z}}_q^n$.

• To encrypt a message $b$, pick $A$ at random and pick $e$.

  $$c=As+e+(0,\mathrm{\dots },0,b\cdot \lfloor q/2\rfloor .)$$ (146)

• Send $(A,c)$.

• To decrypt, output $rounding(c-As)$.

Public-key scheme:

The only difference is that we treat $A,As+e$ as the public-key, and treat $s$ as the secret key.

• Randomness $r\in {\{0,1\}}^m$. Encrypt: $(r^{T}A,r^T(As+e)+b\lfloor q/2\rfloor )$

• Decrypt $(c_1,c_2)$: round $c_2-c_1^{T}s$.

Security of the Public-key scheme.

We can show $r^T[Au]+(0,\mathrm{\dots },0,b\lfloor q/2\rfloor )$ is indistinguishable to uniform by the following lemma.

Lemma 9 (Leftover Hash).

For $m\gg n\log n$, and $r$ uniformly at random, then the following two distributions are statistically close:

$$(A,r^{T}A),(A,u).$$ (147)

11.4 Worst-case to average-case reduction

Start with a distribution $D$ over $s$, such that $(A,As+e)$ is hard.

Sample $\widehat{s}$ uniformly at random, $(A,As+e+A\widehat{s})$.

12 Quantum Computing

Consider qubit $|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$, and $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$.

Definition 12.1 (Quantum circuits.).

A quantum circuit is defined by a unitary matrix $U$ ($U^{T}U=I$), so that

$$⟨\psi \left|U^{T}U\right|\psi ⟩=⟨\psi |\psi ⟩=1.$$ (148)

Definition 12.2 (Universal quantum gates).

• Toffoli: $T|a,b,c⟩=|a,b,ab\oplus c⟩$.

• Hadamard: $H|0⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$, and $H|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩$.

One can check that both gates are unitary.

12.1 Efficient period finding

Simon’s problem. Input a black-box function $f:{\{0,1\}}^n\to {\{0,1\}}^n$. Promise that there exists $s\in {\{0,1\}}^n$, $f(x)=f(x+s)$. How to find $s$?

Classical algorithms take exponential time.

Quantum speedup.

• Create a uniform superposition: $\frac{1}{\sqrt{2^n}}{\sum }_x|x⟩$ by $H|0⟩$.

• Apply $f$ in superposition:

  $$\frac{1}{\sqrt{2^n}}\underset{x}{\sum }|x⟩|0^n⟩\to \frac{1}{\sqrt{2^n}}\underset{x}{\sum }|x⟩|f(x)⟩.$$ (149)

  Note that this operation is unitary (reversible) as we can subtract $f(x)$ to recover.

• Measure the second register. If we measure $y\in {\{0,1\}}^n$, the probability of $y$ is $2\cdot \frac{1}{\sqrt{2^n}}$, and the remaining state

  $$\frac{1}{\sqrt{2}}(|x⟩+|x\oplus s⟩),s.t.f(x)=f(x+\oplus s)=y.$$ (150)

• Apply $H^{\oplus n}$.

  $$\frac{1}{\sqrt{2\cdot 2^n}}(\sum _y{(-1)}^{x\cdot y}(1+{(-1)}^{y\cdot s})|y⟩)$$ (151)

  Notice that $1+{(-1)}^{y\cdot s}=0$ if $y\cdot s=1$.

• Sample many $y$ to get linear equations $y\cdot s=0$. Solve $s$.

12.2 Reduction of factorization to period finding

Factoring: $N=pq$, find $p,q$.

• Find with $(a,N)=1$.

• Construct function $f(x)=a^x(modN)$. So $f(x)=f(x+r)$ if and only if $x^r=1(modN)$. We can thus find $r$.

  Lemma 10.

  If $N=pq$, chosen uniformly at random and $(a,N)=1$, then with probability $\ge 1/2$, $r$ is even and $a^{r/2}\ne \pm 1(modN)$.

• $(a^{r/2}+1)(a^{r/2}-1)=0(modN)$. Then $gcd(N,a^{r/2}+1)$ is a nontrivial factor of $N$.