\documentclass[10pt]{article}
\usepackage{amssymb}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{20}{April 19, 2007}{Ronitt Rubinfeld}{Erdong Chen}

%%%% body goes in here %%%%
\section{Graph Isomorphism $\cong$}

We talked about a lower bound last time. Recall from last lecture
(all are based on adjacent matrix model):

\begin{tabular}{|l|c|c|} \hline
   Thm               &  H known   & H unknown  \\ \hline
   1-sided error &  $\tilde{\Theta}(n)$ & $\tilde{\Theta}(n^{\frac{3}{2}})$  \\ \hline
   2-sided error &  $\tilde{\Theta}(\sqrt{n})$ & $\Omega(n), \tilde{O}(n^{\frac{5}{4}}) $  \\ \hline
\end{tabular}

Difference between the case that $H$ is known and $H$ is unknown:
when $H$ is known, query complexity to $H$ is zero. We will discuss
two upper bounds in today's class.

\subsection{1-Sided Tester}
In this subsection, we will discuss the upper bound of 1-sided
testers when $H$ is known.
\begin{lemma}
When $H$ is known, there is a 1-sided tester with
$\tilde{\Theta}(n)$ queries.
\end{lemma}
\begin{proof}

\textbf{Algorithm:}

\begin{itemize}
\item[1] $Q\leftarrow$ pick each edge slot with probablity
$\frac{\ln{n}}{\varepsilon n}$ i.i.d. (no queries yet!)
\item[2] if $|Q|\le \frac{10n\ln{n}}{\varepsilon}$, ACCEPT,
else ask queries in $Q$ of $G$.
\item[3] if there is a isomorphism from $G$ to $H$ consistent with
$Q$, ACCEPT
\end{itemize}

runtime: $O(\frac{n!n\ln{n}}{\varepsilon})$ (because $n!$ different
permutations exist)

query complexity:$O(\frac{n\ln{n}}{\varepsilon})$

\textbf{Behavior:}

\begin{itemize}
\item If $G\cong H$, algorithm always accepts.
\item IF $G$ is $\varepsilon$-far from isomorphic to $H$

\[\forall \textrm{ permuation } \pi, d(\pi(G),H) = \frac{\textrm{symmetric distance of
adjacent matrix of $\pi(G) and H$}}{n^2} \ge \varepsilon\]

Thus, Pr[accept in step 2] is $o(1)$ (smaller than any constant).

By Chernoff bounds, we will have:

\[E[|Q|] = \frac{n^2\ln{n}}{\varepsilon n} = \frac{n
\ln{n}}{\varepsilon}\]

If reach Step 3:

$\forall \textrm{ permuation } \pi: V_G\rightarrow V_H$ \\$\exists
E_{\pi} s.t. |E_{\pi}| \ge \varepsilon n^2 \& \forall (u,v) \in
E_{\pi}, (u,v) \in E_{\pi(G)} \vartriangle E_H$,

where $\vartriangle$ is the operator of symmetric difference, and
(u,v) is denoted as a witness against $\pi$.

\[\forall (u,v) \in E_{\pi}, \textrm{Pr}[(u,v) not \in Q] = 1 -
\frac{\ln{n}}{\varepsilon n}\]

\[\textrm{Pr}[\forall (u,v) \in E_{\pi}, (u,v) not \in Q] = (1 -
\frac{\ln{n}}{\varepsilon n})^{\varepsilon n^2}\]

By union bound,
\[\textrm{Pr}[\exists \pi \textrm{ s.t. } \forall (u,v) \in E_{\pi},
(u,v) not \in Q] \le n!(1 - \frac{\ln{n}}{\varepsilon
n})^{\varepsilon n^2}\]
\[\le n! (e^{-\frac{\ln{n}}{\varepsilon n}})^{\varepsilon n^2} \le n! \frac{1}{n^n} = o(1)\]

Thus, Pr[accept] is smaller than any constant.

\end{itemize}

By the analysis above, the algorithm with $\tilde{\Theta}(n)$
queries is correct.
\end{proof}

\subsection{2-Sided Tester}
In this subsection, we will discuss the upper bound on 2-sided
testers when $H$ is known. We will discuss this based on a special
case, and please refer the paper for full proof.

\begin{lemma}
When $H$ is known, a 2-sided tester needs only $\tilde{O}(\sqrt{n})$
queries.
\end{lemma}
\textbf{Very special case:} Assume a graph $H$ is s.t. $\forall
u,v, d_{u,v} \equiv \frac{1}{n} | \{N(u) \vartriangle N(v)\}| > \epsilon/4$, 
where
$\vartriangle$ is the operator of symmetric difference, $N(v)$ is
the set of all neighbors of $v$ .

\begin{definition}
For any $C \subseteqq V$, define C-labeling of any $v\in V$ : set of
neighbors $N(v) \cap C$ is represented by a string of length $|C|$,
while the string is denoted by $\textrm{label}_c(v)$.
\end{definition}

Note: There are at most $2^{|C|}$ possible labels. 
Note that an $n$-node graph can have at most 
$n$ distinct labels.

In our special case, since we have $\forall u,v, d_{u,v} >
\frac{\varepsilon }{4}$, if we
pick $c = {\log{n}}^2$ random vertices (call it a "core set"),
then

$\forall u,v, \textrm{Pr} [\textrm{label}_c(u) =\textrm{label}_c(v)]
\le (1-\frac{\varepsilon}{4})^{{\log{n}}^2} = n
^{-\frac{\varepsilon}{4}\log{n}}$

and thus,$ \textrm{Pr} [\forall u,v, \textrm{label}_c(u)
=\textrm{label}_c(v)] \le (1-\frac{\varepsilon}{4})^{{\log{n}}^2} =
n^2 n ^{-\frac{\varepsilon}{4}\log{n}} = o(1)$

\textbf{Idea of Algorithm:}
\begin{itemize}
\item[1(a)] pick $C (={\log{n}}^2)$ nodes in unknown graph
\item[1(b)] query all edges in $C$'s subgraph
\item[2] Pick $n^{\frac{1}{8}}$ (much less for the special case)
nodes in $G$, and find all the $C$-labels.
\item[3] Pair up $n^{\frac{1}{8}}$ nodes, and then query edges of
each pair in $G$.
\item[4] For each $C'$, and for each mapping $\pi_{C,C'}$

let $\tilde{\pi} \leftarrow$ permutation from $G$ to $H$ consistent with
$\pi_{C,C'}$. (We will prove that only one such mapping exists
later)

$\forall$ pairs $(u,v)$ in Step 3, if $\exists$ edge between exactly
one of $(u,v) \in \left\{ \tilde{\pi(u)}, \tilde{\pi(v)}\right\}$,
reject $\tilde{\pi}$ and $\pi_{C,C'}$. Such pair $(u,v)$ is called a
witness against $\tilde{\pi}$.
\end{itemize}
\textbf{Claim:} In our special case, $\tilde{\pi}$ is unique if it
exists at all(maybe no way to map from $C$ to $C'$)

\begin{itemize}
\item If $\textrm{label}_{C}(X) = \textrm{label}_{\pi_{C,C'}}(X) $, then
$\tilde{\pi}$ maps $x$ to $y$.
\item If no such $y$, then $G \not\cong H$.
\item if there is more than one such $y$, then $G \not\cong H$ or we
were unlucky with choice of labels.
\end{itemize}

\textbf{Behavior:}

if $G\cong H$, $\tilde{\pi}$ exists that no witness is found

if $G$ is $\varepsilon$-far from $H$,

$\forall \tilde{\pi}$ in Step 4, Pr$[\tilde{\pi} \textrm{ passes
Step 4}] \le (1-\varepsilon) ^ {n^{\frac{1}{8}}}$ (each edge passes
with probability $1-\varepsilon$)
\[\le e^{-\varepsilon n^{\frac{1}{8}}} = o(\alpha^{-{\log{n}}^3})\]

Thus, Pr[any $\tilde{\pi}$ passes] $\le O(n^{{\log{n}}^2}
\alpha^{-{\log{n}}^3}) = O(\alpha^{{\log{n}}^2}
\alpha^{-{\log{n}}^3}) \le \frac{1}{4}$.

\end{document}