
\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{hyperref}
%\usepackage{amsthm}
\newtheorem{define}{Definition}


%\newcommand{\Z}{{\bf Z}}
%\usepackage{psfig}

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

\input{defs.tex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Definitions: If you want to add definitions commands and macros to the
%% scribe, please do it in this space
\newenvironment{useful-facts}{\bigskip{}\noindent{\bf Useful facts}\hspace*{1em}}{\bigskip}
\newcommand{\f}{f:\{\pm1\}^n\to\R}
\newcommand{\g}{g:\{\pm1\}^n\to\{\pm1,0\}}
\newcommand{\eps}{\varepsilon}
\newcommand{\sign}{\rm sign}
\newcommand{\V}{\mathbb{V}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Heading: In the parentheses below, write the sequential number of the
%% talk, the talk date, the name of the speaker, and the name or names of
%% whoever wrote the scribe (seperated by commas).
\lecture{13}{June 2, 2008}{Guy Kindler}{Ora Hafets}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In the privious lecture we saw the Bonami-Beckner transform and some corollaries.
Today we will see some more related theorems, like Freidgut's theorem, KKL and BKKKL.

%reminder - forgot how to write a new section...
But first - a reminder of a corollary we want to use,
\begin{corollary}\label{cor:bonami} If $1\leq p\leq 2\leq q<\infty$ then
$$ \norm{f^{\leq k}}_q \leq (q-1)^{k/2}\norm{f}_2 $$
$$ \norm{f^{\leq k}}_2 \leq (p-1)^{-k/2}\norm{f}_p $$
\end{corollary}

%new lecture - how do I do that?...
Now we can state the following corollary:

\begin{corollary}\label{cor:short-corr} Let $\g$. Then
$\norm{g^{\leq k}}_2^2 \leq 2^k(\norm{g}_2^2)^{4/3}$.
\end{corollary}
\begin{proof}
Corollary \ref{cor:bonami} with $p=\frac{3}{2}$ implies $\norm{g^{\leq k}}_2^2 \leq 2^k\norm{g}_{3/2}^2$. Since $g$ gets only the values $\{\pm1,0\}$,
$\norm{g}_{3/2}^{3/2} = \norm{g}_2^2$, so we have $2^k(\norm{g}_{3/2}^2) = 2^k\left(\norm{g}_2^2\right)^{4/3}$.
\end{proof}

This corollary helps us in proving an important theorem that says that low influence functions are juntas,
\begin{theorem}[Freidgut '95] Let $f:\{\pm1\}^n\to\{\pm1\}$ s.t. $I({f})\leq{k}$. Then $f$ is a $\left(4\eps,\frac{8k^2 2^{\frac{6k}{\eps}}}{\eps^3}\right)$-junta.
\end{theorem}
\begin{proof}
Define $t = \frac{\eps^3}{8k^3}2^{-\frac{6k}{\eps}}$, $J = \{i\in[n] \ \vert\ I_i(f)\geq{t}\}$.
Then obviously $|J|\leq\frac{k}{t} = \frac{8k^2 2^{\frac{6k}{\eps}}}{\eps^3}$.

Define $g = \sum_{S\subseteq{J}}{\hat{f}(S)\chi_S}$.
It's enough to prove $\norm{f-g}_2^2 \leq \eps$, because it implies: $\norm{f - \sign(g)}_2^2\leq{4\eps}$, which gives the theorem.

We prove $\norm{f-g}_2^2 \leq \eps$ in two parts, first for low frequencies and then for high frequencies:
\begin{eqnarray*}\label{eq:barak}
\sum_{{S\setminus{J}\neq\emptyset} \atop {|S|\leq\frac{2k}{\eps}}}{\hat{f}(S)^2}
 & \leq & \sum_{{S\setminus{J}\neq\emptyset} \atop {|S|\leq\frac{2k}{\eps}}}{|S\setminus{J}| \hat{f}(S)^2} \\
 & = & \sum_{i\in{[n]\setminus{J}}}{\norm{f_i^{\leq\frac{2k}{\eps}}}_2^2} \\
 & \leq & 2^{\frac{2k}{\eps}} \sum_{i\in{[n]\setminus{J}}}{\left(\norm{f_i}_2^2\right)^{\frac{4}{3}}} 
 \text{\quad (By corollary \ref{cor:short-corr})} \\
 & \leq & 2^{\frac{2k}{\eps}} \cdot \max_{i\in{[n]\setminus{J}}}{\{I_i(f)^{\frac{1}{3}}\}} \cdot\sum_i{I_i(f)}\\
 & \leq & 2^{\frac{2k}{\eps}} \cdot \max_{i\in{[n]\setminus{J}}}{\{I_i(f)^{\frac{1}{3}}\}} \cdot I({f})\\
 & \leq & 2^{\frac{2k}{\eps}} \cdot t^{\frac{1}{3}} \cdot k 
 \text{\quad(recall that $J = \{i\in[n] \ \vert\ I_i(f)\geq{t}\}$ )} \\
 & \leq & \frac{\eps}{2}
 \text{\quad(follows from $t = \frac{\eps^3}{8k^3}2^{-\frac{6k}{\eps}}$)}
\end{eqnarray*}

%\begin{eqnarray}
%$\sum_{{S\setminus{J}\neq\emptyset} {|S|\leq\frac{2k}{\eps}}}{\hat{f}(S)^2}$
% & \leq & $\sum_{S\setminus{J}\neq\emptyset |S|\leq\frac{2k}{\eps}}{|S\setminus{J}| \hat{f}(S)^2}$ \\
%& = & $\sum_{i\in{[n]\setminus{J}}}{\norm{f_i^{\leq\frac{2k}{\eps}}}_2^2}$ \\
%& \leq & $2^{\frac{2k}{\eps}} \sum_{i\in{[n]\setminus{J}}}{\left(\norm{f_i}_2^2\right)^{\frac{4}{3}}}$ \\
%& & \text{(By corollary \ref{cor:short-corr})} \\
%& \leq & $2^{\frac{2k}{\eps}} \cdot \max_{i\in{[n]\setminus{J}}}{\{I_i(f)^{\frac{1}{3}}\}} \cdot\sum_i{I_i(f)}$\\
%& $\leq$ & $2^{\frac{2k}{\eps}} \cdot \max_{i\in{[n]\setminus{J}}}{\{I_i(f)^{\frac{1}{3}}\}} \cdot I({f})$\\
%& \leq & $2^{\frac{2k}{\eps}} \cdot t^{\frac{1}{3}} \cdot k$ \\
%& & \intertext{(recall that $J = \{i\in[n] \ \vert\ I_i(f)\geq{t}\}$ )}
%& \leq & \frac{\eps}{2}
%\end{eqnarray}

We now deal with the high frequencies:

\begin{eqnarray*}
\sum_{{S\setminus{J}\neq\emptyset} {|S|>\frac{2k}{\eps}}}{\hat{f}(S)^2} & \leq &
\sum_{|S|>\frac{2k}{\eps}}{\hat{f}(S)^2} \\
& \leq & \frac{\eps}{2k} \sum_S{|S|\hat{f}(S)^2} \\
& \leq & \frac{\eps}{2k} \cdot k \\
& \leq & \frac{\eps}{2}
\end{eqnarray*}
From the two inequalities above we have $\norm{f-g}_2^2 = \sum_{S\setminus{J}\neq\emptyset}{\hat{f}(S)^2} \leq \frac{\eps}{2}+\frac{\eps}{2} =\eps$, as we wanted.
\end{proof}

The next result is that $\exists{\delta_0 >0}$ such that the following holds,
\begin{theorem} [KKL] \label{theorem:KKL}
Let $f:\{\pm1\}^n\to\{\pm1\}$, $0<\delta<\delta_0$.
If  
\begin{equation}\label{eq:kkl}
I(f)\leq \frac{1}{20}\left(\left(1-\hat{f}(\emptyset)^2\right)\log{\frac{1}{\delta}}\right)
\end{equation}
then $\exists{i}$ s.t. $I_i(f)>\delta$.
\end{theorem}
If $f$ is constant then the theorem is obvious, so we assume that $f$ is balanced.

\begin{proof}
The function $f$ is balanced, so $\hat{f}(\emptyset)^2 \neq 1$.
Define $k = \frac{2I(f)}{1-\hat{f}(\emptyset)^2}$. Then:
\begin{eqnarray}
\sum_{|S|>k}{\hat{f}(S)^2} & \leq & \frac{1}{k}\cdot\sum_{|S|>k}{|S|\hat{f}(S)^2} 
\leq \frac{1}{k}\cdot\sum_S{|S|\hat{f}(S)^2} 
= \frac{I(f)}{k} 
= \frac{1-\hat{f}(\emptyset)^2}{2}
\end{eqnarray}
Now:
\begin{eqnarray*}
\frac{1-\hat{f}(\emptyset)^2}{2} & = & 1-\hat{f}(\emptyset)^2 - \frac{1-\hat{f}(\emptyset)^2}{2} \\
& \leq & \sum_{|S|>0}{\hat{f}(S)^2} - \sum_{|S|>k}{\hat{f}(S)^2} \\
& = & \sum_{0<|S|\leq{k}}{\hat{f}(S)^2} \\
& \leq & \sum_{|S|\leq{k}}{|S|\hat{f}(S)^2} \\
& = & \sum_{i\in{[n]}}{\norm{f_i^{\leq{k}}}_2^2} \\
& \leq & 2^k \sum_{i\in{[n]}}{\left( \norm{f_i^{\leq{k}}} \right)^{\frac{4}{3}}} 
\text{\quad(By corollary \ref{cor:short-corr})} \\
& \leq & 2^k\cdot\max_i{\{I_i(f)^{\frac{1}{3}}\}}\cdot I(f) 
\text{\quad(similar to the privious proof)} \\
& \leq & \left(\frac{1}{\delta}\right)^{10} \cdot \max_i{\{I_i(f)^{\frac{1}{3}}\}} \cdot I(f)
\text{\quad(Because $2^k \leq 2^{\frac{\log{\frac{1}{\delta}}}{10}}$ )} \\
& \leq & \left(\frac{1}{\delta}\right)^{10} \cdot \max_i{\{I_i(f)^{\frac{1}{3}}\}} \cdot\frac{1-\hat{f}(\emptyset)^2}{20} \cdot \log{\frac{1}{\delta}}
\text{\quad(By \ref{eq:kkl})}
\end{eqnarray*}
Therefore:
$$
max_i{\{I_i(f)\}} \geq 8000\cdot\delta^{\frac{3}{10}}\cdot\left(\frac{1}{\log{\frac{1}{\delta}}}\right)^3 > \delta
$$
\end{proof}

If $\delta = \frac{\log{n}}{n}$, then the theorem implies the following two corollaries,
\begin{corollary}
If $f$ is balanced and $I(f)<C\log{n}$, then $\exists{i}$ s.t. $I_i(f)>\frac{\log{n}}{n}$.
\end{corollary}

\begin{corollary}
If $f$ is boolean, balanced and transitive, then $I(f)\geq C\log{n}$.
\end{corollary}

We want to state another interesting result, but to do that we need the following definition,
\begin{define}
Let $f:\{\pm1\}^n\to\{\pm1\}$.
$$ I_i^\prime(f) = \Pr_{x\setminus{i}}{\left(f(x) \text{ non constant on } x_i\right)} $$
$$ I^\prime(f) = \sum_i{I_i^\prime(f)} $$
\end{define}

\begin{theorem}[BKKKL]
Let $f:\{\pm1\}^n\to\{\pm1\}$, $t=E(f)$. Then $\exists{i}$ s.t. $I_i^\prime(f)\geq C(1-t^2)\frac{\log{n}}{n}$.
\end{theorem}

We will talk more about this theorem in our next class.
\end{document}
