
\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

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

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{17}{April 10, 2007}{Ronitt Rubinfeld}{Jacob Scott}



\section{Alon's Theorem (adjacency matrix model)}

\begin{theorem}
Let $H$ be a fixed graph with $|H| =h$, and $P_H$ be the property of not having $H$ as a subgraph. Then, 

\begin{enumerate}
\item If $H$ is bipartite:

\begin{enumerate}
\item $\exists$ a 2-sided tester for $P(H)$ with $O(1/\epsilon)$ queries
\item $\exists$ a 1-sided tester for $P(H)$ with $O(h^2(1/\epsilon)^{h^2/4})$ queries
\end{enumerate}

\item
If $H$ is \textsl{not} bipartite, $\exists c$ such that any $1-$sided error tester needs $\geq (\frac{c}{\epsilon})^{c \log (1/\epsilon)}$
\end{enumerate}
\end{theorem}

We will prove $(2)$ for triangles, that is, that testing triangle-freeness with 1-sided error requires queries superpolynomial in $\epsilon$.

\section{Structure of the Algorithm (Goldreich Trevisan)}

\begin{theorem}Let $P$ be any graph property (in the adjacency matrix model). Suppose $T$ is a tester for $P$ with query complexity $q(n,\epsilon)$. Then there is a tester $T'$ for $P$ such that $T'$ has the following form:

\begin{enumerate}
\item Select a random subset of $2q(n,\epsilon)$ nodes
\item Query all pairs in subset
\item Flip coins and make a decision
\end{enumerate}
If $T$ has 1-sided error, then so does $T'$.
\end{theorem}

We note the following important properties of $T'$:

\begin{enumerate}
\item $T'$ has query complexity $O((q(n,\epsilon))^2)$
\item $T'$ is non-adaptive
\item If, and only if,  $T'$ cannot decide $P$ in $O(q''(n,\epsilon))$ queries, then $T$ cannot decide $P$ in $O(\sqrt{q''(n,\epsilon)}$ queries
\end{enumerate}

Thus, a superpolynomial lower bound for $T'$ implies a superpolynomial bound for $T$. We later show lower bounds for such a $T'$ and by Goldreich-Trevisan can conclude that our bounds apply to all testers.

\section{Number Theory Lemma}
\begin{lemma}
 $\forall m, \exists X \subset M = \{1,2,\ldots,m\}$ of size at least $|X| > e^{m/(10\sqrt{\log m})}$, with no nontrivial solution to $X_1 + X_2 = 2 X_3$ (i.e., the only solution is  $X_1 = X_2 = X_3$).
\end{lemma}
\textbf{Proof:}\\
Let $d$ be an integer, and $k = \lfloor \frac{\log m}{\log d} \rfloor - 1$. \\

\begin{define} 
Let $W_B = \left\{ \sum_{i=0}^{k} X_i d^i | \forall i \  X_i < d/2, \land  \sum X_i^2 = B \right\}$, where $B$ is chosen to maximize $|W_B|$.
\end{define}

Consider $x \in W_B$ as a base $d$ vector, $x = [x_0, x_1, \ldots, x_k]$. Note that adding together two elements in $W_B$ will result in a vector whose maximum value is $d-1$, thus not causing any `carries'. Furthermore, $\max_x x \in W_B \leq \sum_{i=0}^{k} \frac{d}{2}d^i \leq d^{k+1} \leq d^{ \lfloor \frac{\log m}{\log d} \rfloor } \leq d^{\log_d m} \leq m$. 


\begin{fact} 
The Sum Property states that given $x,y,z \in W_B$,
$x+ y = 2z \Leftrightarrow x_i + y_i = 2 z_i$ for all $i$. 
\end{fact}
\textbf{Proof of Fact:}
\begin{eqnarray*}
\forall q \in W_B, \sum_{i=1}^{k} q_i d^i &=& B\\
x+ y = 2z  &\Leftrightarrow& \sum_{i=1}^{k} x_i d^i + \sum_{i=1}^{k} y_i d^i  = 2 \sum_{i=1}^{k} z_i d^i\\
&\Leftrightarrow& \forall i, x_i + y_i = 2 z_i
\end{eqnarray*}
Here the last step stems from addition not generating carries for any $d^i$, as mentioned above.
\qed

\begin{claim} If $x_i + y_i = 2z_i$, then $x_{i}^2 + y_{i}^2 \geq 2 z_{i}^2$, with equality if and only if $x_i = y_i = z_i$.
\end{claim}
\textbf{Proof of Claim:}
$f(a) = a^2$ is convex.
By Jensen's inequality, $\sum_{i=1}^{n} f(a_i)/n \geq f(\sum a_i / n)$ with equality only if all $a_i$ are identical.
\qed\\
\textbf{Proof of Lemma:}

First, we prove that all solutions to $x + y = 2z$ must be trivial. Since $\forall q \in W_B, \sum_{i=1}^{k} q_i d^i = B$, it must be the case that $\sum x_{i}^2 + \sum y_{i}^2 = 2B = 2 \sum z_{i}^2$. By the Sum Property and the claim, for each $i$, $x_{i}^2 + y_{i}^2 \geq 2 z_{i}^2$. However, if $\neg (x= y = z)$ then  $\exists i$ such that $\neg(x_i = y_i = z_i)$. By the claim, it must then be that $x_{i}^2 + y_{i}^2 > 2z_{i}^2$. But $\forall$ $j \neq i$, $ x_{j}^2 + y_{j}^2 \geq 2z_{j}^2$. Thus, if $\exists i$ such that  $\neg(x_i = y_i = z_i)$, then $\sum_i x_{i}^2 + \sum_i y_{i}^2 > 2 \sum_i z_{i}^2$, which is a contradiction. Therefor, $\forall i, x_i = y_i = z_i$, $x = y = z$, and all solutions are trivial.\\

Finally, we must consider the size $|W_B|$ of $W_B$.  From the definition, we know that $B \leq (k+1)(d/2)^2 \leq kd^2$. It is also the case that every vector $v$ with entries $< d/2$ has $\sum_i v_i^2 = B_j$ for some $B_j$. Thus 

$$\sum_B |W_B| = | \cup W_B | \geq (d/2)^{k+1} > (d/2)^k$$

By the pigeonhole principle, we conclude that $\exists j$ such that $W_{B_j}$ is of size $\geq (d/2)^k/(kd^2)$.If we set $d = e^{10 \sqrt{\log m}}$, then $k \approx \sqrt{\log m}/10$, and  $|W_B| = |W_{B_j}| \geq e^{m/(10\sqrt{\log m})}$, which proves the Lemma. \qed

\section{Next Lecture}
In the next lecture we will combine Goldreich-Trevisan with our number theory lemma to produce hard graphs for which any tester  for  1-sided triangle freeness requires   $\geq (\frac{c}{\epsilon})^{c \log (1/\epsilon)}$ queries.



\end{document}




