diff options
Diffstat (limited to 'ps3')
| -rw-r--r-- | ps3/main.tex | 84 |
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} |