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

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

% pseudocode package:
\usepackage[noend]{algorithm2e}
\incmargin{1em}
\restylealgo{unboxed}
\linesnumbered
\dontprintsemicolon
\SetArgSty{rm}
\SetTitleSty{textsc}{11pt}
\SetKwComment{Comment}{ // }{}

% custom commands:
\newcommand{\textbi}[1]{\textbf{\textit{#1}}}
\newcommand{\la}{\leftarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\NL}{\textrm{NL}}
\renewcommand{\L}{\textrm{L}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\Obj}{\textrm{Obj}}
\newcommand{\eps}{\varepsilon}
\newcommand{\La}{\Leftarrow}

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

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{13}{March 20, 2007}{Ronitt Rubinfeld}{Huy Ngoc Nguyen}

%%%% body goes in here %%%%
\section{Bipartiteness testing on dense graph}
\begin{define}
$G$ is "{$\epsilon -far$}" from bipartiteness if must remove at least $\epsilon n^2$ edges to make it bipartite.
\end{define}

\begin{define}
(equivalent to definition 1) $\forall$ partitions $(V_1,V_2)$ of $V$ there are at least $\epsilon n^2$ edges $(w,v)$ s.t either $u,v \in V_1$ or $u,v \in V_2$ (in this case $(u,v)$ is a {\bf violating pair}).
\end{define}


\noindent{\bf Algorithm (1): }: \\
TestBipartite($A$,$G$)     \textit{($A$ - adjacency matrix for $G$)} \\
\begin{algorithm}[H]
	choose sample $S$ uniformly s.t $|S| = \Theta(\frac{1}{\epsilon^2}\log{\frac{1}{\epsilon}})$ \;
	query $A(u,v)$ $\forall u,v \in S$. \;
	FAIL if subgraph not bipartite else PASS. 
\end{algorithm}
\textrm{ Note: total number of queries :} $O(\frac{1}{\eps^4}\log^2{\frac{1}{\eps}})$ 

\begin{theorem} The algorithm is a property tester for bipartiteness. More precisely,
\begin{itemize} 
\item[(1)] if $G$ is bipartite, \textrm{TestBipartite} PASSES.
\item[(2)] if $G$ is $\eps-far$ from bipartiteness, $Pr\left[\textrm{ TestBipartite FAILS } \right] \geq \frac{3}{4}$ .
\end{itemize}
\end{theorem}

\begin{proof}
Consider the following algorithm,

\noindent{\bf Algorithm (2)}: 

\begin{algorithm}[H]
  Choose $U$ uniformly, s.t $|U| = O\left(\frac{1}{\eps}\log{\frac{1}{\eps}}\right)$ \;
  Choose a bunch of pairs $(u_i,v_i) \ra W$ ($|W| = m = O\left(\frac{1}{\eps^2}\log{\frac{1}{\eps}}\right)$) \;
	Query $(u,v)$ $\forall u,v \in U$ \;
	Query $(u_i,v_i) \in W$ \;
	Query all edges $(w,u_i)$, $(w,v_i)$ for $w\in U$ and $(u_i,v_i) \in W$.  \;
	FAIL if no bipartite partition possible.	 
\end{algorithm}

Since $|U|$ and $|W|$ is $O\left(\frac{1}{\eps^2}\log{\frac{1}{\eps}}\right)$, we can consider $U$ and $W$ in this algorithm as subsets of $S$ in algorithm (1). Therefore, to prove algorithm (1), it is sufficient to prove that the algorithm (2) is a property tester for bipartiteness. \\

Firstly, consider a special case when all nodes in $V$ connected to $U$, $U$ is "bad" if there is no partition of $U$ into $(U_1,U_2)$  that induces a consistent partition of $(V_1,V_2)$ in $V$. It will be shown that the algorithm will output FAIL with high probability when $U$ is "`bad". \\


\noindent Consider a bipartition $(U_1,U_2)$ of $U$, a bipartition of $V$ can be induced from $(U_1,U_2)$ by the following algorithm\\
\noindent{\bf Bipartition Algorithm:} 

\begin{algorithm}[H]
	Put $U_1$ into $V_1$ \;
	Put $U_2$ into $V_2$ \;
	{$\forall v \in V \setminus (U_1 \cup U_2)$ :
\begin{itemize}
	\item  if $v$ is adjacent to a node in $U_1$ place $v$ in $V_2$
	\item  if $v$ is adjacent to a node in $U_2$ place $v$ in $V_1$
	\item  if placed in both, choose arbitrarily.
\end{itemize} }
\end{algorithm}

\noindent Note: Every node get placed in time $O(|U|)$. Therefore, given any edge $(u,v)$, we can detect if it violates $(U_1,U_2)$ (i.e showing that $(U_1,U_2)$ not leading to bipartition) in $O(|U|)$ time. \\

\begin{define}{}
$W$ is \textit{"not compatible"} with $(U_1,U_2)$ if cant partition nodes in $W$ (touched by edges in $W$) into $\tilde{W} = (\tilde{W_1},\tilde{W_2})$ s.t $((\tilde{W_1}\cup U_1),(\tilde{W_2} \cup U_2))$ is a bipartition
\end{define}

\noindent $\Rightarrow$ Algorithm (1), (2) reject if there is no compatible $W$ for any bipartition $(U_1, U_2)$ of $U$.

\begin{define}{.}
\begin{itemize}
\item[(1)] $\textrm{ A node } w \textrm{ is "witness" against } (U_1,U_2) \textrm{ if } \exists u_1 \in U_1, u_2 \in U_2 \textrm{ s.t } (w,u1) \textrm{ and } (w,u_2) \in E$.
\item[(2)] An edge $(w_1,w_2)$ is "witness" against $(U_1,U_2)$ if $\exists u_1,u_2$ s.t : 
\begin{itemize}
	\item $u_1,u_2 \in U_1$ or $u_1,u_2 \in U_2$.
	\item $(w,u_1), (w,u_2) \in E$.
\end{itemize}
\end{itemize}
\end{define}

\noindent Therefore, $\forall$ bipartition $(U_1, U_2)$, if there are at least $\eps n^2$ violating edges, each gives witness against $(U_1,U_2)$: 
\begin{center}
	$Pr\left[ \textrm{ catch a pair in } W \textrm{ witness against } (U_1,U_2) \right] \geq \eps.$ 	
\end{center}
Thus,
\begin{eqnarray*}
Pr\left[ (U_1,U_2) \textrm{ survives } W \right] &\leq& (1-\eps)^{|W|} \\ 
&\leq& \frac{1}{8}2^{-|W|}
\end{eqnarray*}
Since $|W| = \Theta(\frac{|U|}{\eps})$
\begin{eqnarray*}
Pr\left[ \textrm{ any partition of } U \textrm{ survives } W \right] &\leq& \frac{1}{8}2^{-|U|}2^{|U|}\\
&\leq& \frac{1}{8}
\end{eqnarray*}
Although the argument above based on the assumption that $U$ is connected to all nodes in $V$, it is still valid if $U$ is adjacent to "enough" ($\Omega(\eps n^2)$) violating edges . In the remaining of this lecture, we will argue that with high probability when $|U| = \Omega(\frac{1}{\eps}\log\frac{1}{\eps})$, $U$ is adjacent to at least $\frac{\eps n^2}{2}$ violating edges.

\begin{define}
	$v \in V$ is a "high degree" node if $deg(v) \geq \frac{\eps}{4}n$ else v is "low degree".
\end{define}

\begin{lemma}
	By choosing $|U| = \frac{4}{\eps}\log{\frac{32}{\eps}}$, 
\begin{center}
$Pr_U\left[ \textrm{ at most } \frac{\eps}{4}n \textrm{ "high degree" in V dont have enough neighbors in } U \right] \geq \frac{7}{8}$
\end{center}
\end{lemma} 
\begin{proof} 
For each "high degree" $v$ node in $V$, 
\begin{eqnarray*}
Pr\left[\textrm{v has no nbr in U} \right] &\leq& (1 - \frac{\eps n}{4})^{|U|}  \\
&\approx& \frac{1}{e}^{\log{\frac{32}{\eps}}} \\
&=& \frac{\eps}{32}
\end{eqnarray*}
Thus, 
\begin{center}
$E\left[\textrm{number of "high degree" nodes in V that not adjacent to U }\right] \leq \frac{\eps n}{32}$\\
\end{center}
By Markov inequality, 
\begin{center}
$Pr\left[\textrm{number of "high degree" nodes in V that not adjacent to U} \geq \frac{\eps n}{4} \right] \leq \frac{1}{8}$
\end{center}
\end{proof}


\noindent How many edges adjacent either to low degree node or high degree node not adjacent to $U$?
\begin{itemize}
	\item[(1)] adjacent to low degree node $\leq n\frac{\eps}{4}n$
	\item[(2)] adjacent to high degree non-U-neighbor $\leq \frac{\eps n}{4}n$ 	
\end{itemize}
$\Rightarrow$ total $\leq \frac{\eps}{2}n^2$ edges! \\
$\Rightarrow$ at least $\frac{\eps}{2}n^2$ violating edges adjacent to $U$.
\end{proof}
\end{document}