[ps3] end of solutions

1 files changed, 81 insertions, 3 deletions

diff --git a/ps3/main.tex b/ps3/main.tex
index 2cb4a1f..8408e59 100644
--- a/ps3/main.tex
+++ b/ps3/main.tex
@@ -22,6 +22,7 @@
      \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
   {\end{description}}
 
+
 \DeclareMathOperator{\E}{\mathbb{E}}
 \let\P\relax
 \DeclareMathOperator{\P}{\mathbb{P}}
@@ -38,6 +39,7 @@
 \newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
 \newcommand{\llbracket}{[\![}
 
+
 \newtheorem{theorem}{Theorem}
 \newtheorem{lemma}{Lemma}
 \algrenewcommand\algorithmicensure{\textbf{Output:}}
@@ -154,8 +156,8 @@ $e^{-\Omega(t)}$. To summarize:
 \begin{displaymath}
 \P[|M-\mu(f)|\geq \eps]
 \leq 
-\P\left[\frac{1}{t}\sum_t g(x_t) \geq \frac{1}{2}\left]\leq
-\P\left[\frac{1}{t}\sum_t g(x_t) \geq \mu(g)+\lambda+\frac{1}{4}\left]\leq e^{-\Omega(t)}
+\P\left[\frac{1}{t}\sum_t g(x_t) \geq \frac{1}{2}\right]\leq
+\P\left[\frac{1}{t}\sum_t g(x_t) \geq \mu(g)+\lambda+\frac{1}{4}\right]\leq e^{-\Omega(t)}
 \end{displaymath}
 Hence, choosing $t = O(\log\frac{1}{\delta})$ gives the correct success
 probability for our estimator $M$. Furthermore:
@@ -169,6 +171,66 @@ probability for our estimator $M$. Furthermore:
 \end{itemize}
 which satisfies all the requirements.
 
+\section*{Problem 4.8}
+
+For lack of Latex skills, I will denote by $G_1\circledR G_2$ the replacement
+product and by $G_1\circ G_2$ the zig-zag product.
+
+\paragraph{1.} Following the hint, it is easy to see that $G_1\circ G_2$ is
+a subgraph of ($G_1\circledR G_2)^3$. Indeed, one step from $(u,i)$ to $(v, j)$
+in $G_1\circ G_2$ can be seen as the following three steps in $G_1\circledR
+G_2$:
+\begin{enumerate}
+        \item first a step from $(u,i)$ to $(u,i')$
+        \item then a step from $(u, i')$ to $(v, j')$
+        \item then a step from $(v, j')$ to $(v, j)$
+\end{enumerate}
+with the notation that $v$ is the $i'$th neighbor of $u$ and $u$ is the $j'$th
+neighbor of $u$.
+
+Denoting by $Z$ the random walk matrix of $G_1\circ G_2$ and $M$ the random
+walk matrix of $G_1\circledR G_2$ and since $G_1\circ G_2$ is a $D_2^2$
+regular subgraph of $(G_1\circledR G_2)^3$ which is $(D_2+1)^3$ regular, we
+have:
+\begin{displaymath}
+M^3 = \frac{D_2^2}{(D_2+1)^3}Z + \left(1-\frac{D_2^2}{(D_2+1)^3}\right) E
+\end{displaymath}
+where $E$ is the “remainder” and corresponds to random steps in $(G_1\circledR
+G_2)^3$ which are not random steps in $G_1\circ G_2$. Since $Z$ is regular, so
+is $E$, in particular, $\|E\|\leq 1$.
+
+This implies that:
+\begin{displaymath}
+    \lambda(M^3)\leq \frac{D_2^2}{(D_2+1)^3}(1-\gamma_1\gamma_2^2)
+    +\left(1-\frac{D_2^2}{(D_2+1)^3}\right)
+\end{displaymath}
+where we used that the expansion of $G_1\circ G_2$ is at least
+$\gamma_1\gamma_2^2$ using Theorem 4.35. This in turn implies that $G_1\circledR
+G_2$ has expansion at least:
+\begin{displaymath}
+    \left(\gamma_1\gamma_2^2\frac{D_2^2}{(D_2+1)^3}\right)^{1/3}
+\end{displaymath}
+
+\paragraph{2.} Let us consider $G$ a $(N, D, \gamma)$ expander. First if the
+degree of $G$ is even, we can make it odd by adding a new vertex connected to
+all the previous vertices. $N$ increases by one, $D$ increases by one.
+
+Once we have a graph with odd degree $D$, we can take the replacement product
+with the cycle $C$ on $D$ vertices. The cycle is $2$-regular and nonbipartite
+(since $D$ is odd). Hence $G\circledR C$ will be a $(ND, 3, \gamma')$ expander.
+The cycle being nonbipartite, it will have non zero expansion. Part \textbf{1.}
+implies that $\gamma'>0$.
+
+\paragraph{4.} Without loss of generality, assume that $N_1$ is even. Let us
+consider the set $S$ of $N_1D_1/2$ vertices in $G_1\circledR G_2$ where for
+half the clouds, we include all their vertices in $S$. The number of edges
+$e(S, S^C)$ is at most $N_1D_1/2$ since the edges in the cut are the edges from
+the “included” clouds to the non-included ones and each vertex in an included
+cloud is connected to exactly one vertex in an other cloud. Hence $S$ does not
+have edge expansion $\eps$ for $\eps>1/(D_2+1)$. This implies that
+$h(\eps_1,\eps_2, D_2)$ depends on $D_2$. This implies that $g(\gamma_1,
+\gamma_2, D_2)$ also depends on $D_2$ by Theorem 4.14.
+
 \section*{Problem 4.10}
 
 \paragraph{1.} We use a simple counting argument. A set $S$ of at most $K$
@@ -196,7 +258,7 @@ $(1-\eps)D$:
 \end{displaymath}
 on the other hand, we can upper bound $|N(S\cup T)|$:
 \begin{displaymath}
-    |N(S\cup T)|\leq |N(S)| + |N(T)|\leq D|S| + (1-\delta)D|T|
+    |N(S\cup T)|\leq D|S| + (1-\delta)D|T|
     = D\frac{3}{2}|S|-\frac{\delta}{2} D |S|
 \end{displaymath}
 combining the above two inequalities, we obtain:
@@ -210,4 +272,20 @@ N$, pick a random neighbor of $x$ in $G$ and output the bit assigned to this
 neighbor (“1” means $x\in S$, “0” means $x\notin S$). The property $\Pi$ immediately
 implies that the error probability is at most $\delta$.
 
+\paragraph{4.} I follow the hint: if I assign $1$ to $N(S)$, and $0$ elsewhere,
+then using \textbf{2.}, the set $T$ of vertices for which the error probability
+of the query algorithm described in \textbf{3.} is larger than $\delta$ (they
+have at least $\delta D$ neighbors in $N(S)$) is of size at most $|S|/2$.
+
+For each vertex $u\in T$, we can fix it by simply assigning $0$ to $N(u)\cap
+N(S)$. Now this breaks the vertices in $S$ which have at least $\delta D$
+vertices in $N(T)$. But by \textbf{2.} there are at most $|T|/2\leq |S|/4$ such
+vertices, we can fix them by assigning $1$ to the neighbors of these vertices.
+
+By repeating this process, we show that the number of mistakes to fix (number
+of vertices for which the probability of failure is greater than $\delta$) is
+halved each time. Repeating this process at most $\log K/2$ times will lead to
+no mistakes and a valid assignment.
+
+
 \end{document}