\documentclass[11pt,addpoints,answers]{exam}

% Packages
\usepackage{fullpage}
\usepackage{latexsym,amssymb,amsfonts,amsmath,mathrsfs,float, amsthm}
\usepackage[font=small,labelfont=bf, width=.618\textwidth]{caption} % custom captions
\usepackage{xcolor}
\usepackage{tikz, graphics, enumerate}
\usepackage{hyperref}


% Paragraph indentation and spacing
\newcommand{\parset}{
	\setlength{\parskip}{3mm}
  	\setlength{\parindent}{0mm}}
	
% Probability
  \DeclareMathOperator{\var}{Var}
  \renewcommand{\Pr}{\mbox{\rm Pr}}	
  \newcommand{\Exp}{{\mathbb{E}}}
  \newcommand{\E}{\mathbb{E}}

% Sets 
  \newcommand{\R}{\mathbb{R}} % reals
  \newcommand{\C}{\mathbb{C}} % complex numbers
  \newcommand{\N}{\mathbb{N}} % natural numbers
  \newcommand{\Z}{\mathbb{Z}} % integers
  \newcommand{\F}{\mathbb{F}} % field
  \newcommand{\K}{\mathbb K} % field
  \newcommand{\T}{\mathbb T} % circle
\newcommand{\B}{\mathcal{B}} % ball
  \newcommand{\pmset}[1]{\{-1,1\}^{#1}} % hypercube in +-1 basis
  \newcommand{\bset}[1]{\{0,1\}^{#1}} % hypercube
  \newcommand{\sphere}[1]{S^{#1-1}} % real unit sphere of dimension #1
  \newcommand{\ball}[1]{B_{#1}} % real unit ball of dimension $1
  \newcommand{\Orth}[1]{O(\R^{#1})} % orthogonal group
  \DeclareMathOperator{\im}{im} % image
  \DeclareMathOperator{\vspan}{Span} % kernel
  \newcommand{\1}{\mathbf{1}}
  \DeclareMathOperator{\Cball}{\mathcal C}
  \DeclareMathOperator{\cay}{Cay} 
  \DeclareMathOperator{\sol}{Sol} 
\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}

% Miscellaneous
  \newcommand{\st}{:\,} % "such that" to define sets
  \newcommand{\ie}{{i.e.}}  
  \newcommand{\eg}{{e.g.}} 
  \newcommand{\eps}{\varepsilon}
  \newcommand{\ip}[1]{\langle #1 \rangle}
  \newcommand{\cF}{{\mathcal F}}   
  \DeclareMathOperator{\U}{\mathcal{U}}
  \DeclareMathOperator{\sign}{sign}
  \newcommand{\poly}{\mbox{\rm poly}}
  \newcommand{\ceil}[1]{\lceil{#1}\rceil}
  \newcommand{\floor}[1]{\lfloor{#1}\rfloor}
  \DeclareMathOperator{\Tr}{\mathsf{Tr}}
  \DeclareMathOperator{\diag}{diag}
  \DeclareMathOperator{\patt}{patt}
  \DeclareMathOperator{\argmin}{arg\,min}
  \DeclareMathOperator{\spec}{Spec}
  \DeclareMathOperator{\enc}{\sf Enc}
  \DeclareMathOperator{\dec}{\sf Dec}
  \DeclareMathOperator{\diam}{diam} 
  \DeclareMathOperator{\spn}{span} 
  \DeclareMathOperator{\geom}{gm}
\DeclareMathOperator{\sinc}{sinc}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator*{\argmax}{arg\,max}
  \newcommand{\infnorm}{{\ell_\infty, \ldots, \ell_\infty}}
  \newcommand{\pnorm}{{\ell_p,\dots,\ell_p}}
  \newcommand{\tnorm}{{\ell_t,\dots,\ell_t}}
  
  
% Enviroments
  \newcommand{\beq}{\begin{equation}}
  \newcommand{\eeq}{\end{equation}}
  \newcommand{\beqn}{\begin{equation*}}
  \newcommand{\eeqn}{\end{equation*}}
  \newcommand{\beqr}{\begin{eqnarray}}
  \newcommand{\eeqr}{\end{eqnarray}}
  \newcommand{\beqrn}{\begin{eqnarray*}}
  \newcommand{\eeqrn}{\end{eqnarray*}}
  \newcommand{\bmline}{\begin{multline}}
  \newcommand{\emline}{\end{multline}}
  \newcommand{\bmlinen}{\begin{multline*}}
  \newcommand{\emlinen}{\end{multline*}}
  
  \makeatletter

% END OF SUPPLIED VARIABLES

  \chead{\large \textbf{Week 7 Questions}}

  \lhead{\small
    \textbf{{Boolean Functions}\\{Northwestern \\Winter 2021}}}

  \rhead{\small \textbf{Instructor:
     {Shravas Rao}}\\\textbf{Student}: FIRSTNAME LASTNAME}

  \setlength{\headheight}{20pt}
  \setlength{\headsep}{16pt}                       
  \headrule
% execute homework commands

\begin{document}

\pagestyle{head}                % put header on every page

\medskip

\section*{Lecture 12}

\begin{questions}
\question (O 9.2) For $k = 1$, improve the $9$ in the Bonami Lemma to $3$. 
More precisely, suppose $f: \{-1, 1\}^n \rightarrow \R$ has degree at most $1$ and that $x_1, \ldots, x_n$ are independent $3$-reasonable random variables satisfying $\E[x_1] = \E[x_i^3] = 0$.
(For example,the $x_i$’s may be uniform $\pm 1$ bits.) 
Show that $f(x)$ is also $3$-reasonable. 
(Hint: By direct computation, or by running through the Bonami Lemma proof with $k = 1$ more carefully.)
\begin{solution}

  \end{solution}

\question (O 9.3) Let k be a positive multiple of $3$ and let $n \geq 2k$ be an integer. 
Define $f: \{-1, 1\}^n \rightarrow \R$ by
\[
f(x) = \sum_{\substack{S \subseteq [n] \\ |S| = k}} x^S.
\]

\begin{parts}

\part Show that
\[
\E[f^4] \geq \frac{\binom{n}{k/3, k/3, k/3, k/3, k/3, k/3, n-2k}}{\binom{n}{k}^2} \E[f^2]^2
\]
where the numerator of the fraction is a multinomial coefficient – specifically, the number of ways of choosing six disjoint size-$k/3$ subsets of $[n]$. 
(Hint: Given such size-$k/3$ subsets, consider quadruples of size-$k$ subsets that hit each size-$k/3$ subset twice.)
\begin{solution}

  \end{solution}

\part Using Stirling’s Formula, show that
\[
\lim_{n \rightarrow \infty} \frac{\binom{n}{k/3, k/3, k/3, k/3, k/3, k/3, n-2k}}{\binom{n}{k}^2} = \Theta(k^{-2}9^k).
\]
Deduce the following lower bound for the Bonami Lemma: $\|f\|_4 \geq \Omega(k^{-1/2})\cdot \sqrt{3}^k \|f\|_2$.

\begin{solution}

  \end{solution}
\end{parts}

\question (O 9.4) Let $x_1, \ldots, x_n$  be independent, not necessarily identically distributed, random variables satisfying $\E[x_1] = \E[x_i^3] = 0$. 
(This holds if, e.g., each $-x_i$ has the same distribution as $x_i$.) 
Assume also that each $x_i$ is $B$-reasonable.
Let $f = F(x_1, \ldots, x_n)$, where $F$ is a multilinear polynomial of degree at most $k$. Then $f$ is $\max\{B, 9\}^k$-reasonable.


\begin{solution}

  \end{solution}

\question (O 9.20) Show that the KKL Theorem fails for functions$f: \{-1, 1\}^n \rightarrow [-1, 1]$, even under the assumption $\var[f] \geq \Omega(1)$. (Hint: $f(x) = \text{trunc}_{[-1, 1]} (\frac{x_1+\cdots+x_n}{\sqrt{n}})$.)
\begin{solution}

  \end{solution}


\end{questions}

\section*{Lecture 13}

\begin{questions}
\question  (O 7.1) Suppose there is an $r$-query local tester for property $\mathcal{C}$ with rejection rate $\lambda$. 
Show that there is a testing algorithm that, given inputs $0 < \eps, \delta \leq 1/2$ makes $O( \frac{r \log(1/\delta)}{\lambda \eps})$ (nonadaptive) queries to $f$ and satisfies the
following:
\begin{itemize}
\item If $f \in \mathcal{C}$ , then the tester accepts with probability $1$.
\item If $f$ is $\eps$-far from $\mathcal{C}$ , then the tester accepts with probability at most $\delta$.
\end{itemize}
\begin{solution}

\end{solution}

\question (O 7.5) Let $\mathcal{O} = \{w \in \F_2^n\st w \text{ has an odd number of }1\text{’s}\}$. 
Let $T$ be any $n-1$-query string testing algorithm that accepts every $w \in \mathcal{O}$ with probability $1$. 
Show that $T$ in fact accepts every string $v \in \F_2^n$ with probability $1$ (even though $\text{dist}(w,\mathcal{O}) = \frac{1}{n} > 0$ for half of all strings $w$). 
Thus locally testing $O$ requires $n$ queries.
\begin{solution}

  \end{solution}

\question (O 7.6) Let $T$ be a $2$-query testing algorithm for functions $\{-1, 1\}^n \rightarrow \{-1, 1\}$. 
Suppose that $T$ accepts every dictator with probability $1$. 
Show that it also accepts $\text{Maj}_{n'}$ with probability $1$ for every odd $n' < n$. 
This shows that there is no 2-query local tester for dictatorship assuming $n = 2$. 
(Hint: You’ll need to enumerate all predicates on up to 2 bits.)
\begin{solution}

\end{solution}

\end{questions}
\end{document}