\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}