%
% To use this as a template for turning in your solutions, change the flag
% \inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the "author" and "collaborators" fields as
% appropriate. Write your solutions where indicated.
%

\def\inclsolns{0}
\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{amsmath,amssymb,amsthm}

\input{macros}

\theoremstyle{definition}

\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi

\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators given}}
\makeatother


\author{Ada Lovelace}
\collaborators{Charlie Babbage, Mike Faraday}

\begin{document}


\begin{center}
{\Large CS 599B: Math for TCS, Spring 2022}

\bigskip

{\Large Homework 1}

\smallskip

Due: 10:00PM, Friday February 25, 2022 on Gradescope.

\end{center}

\ifnum\inclsolns=1
	\makeatletter
	\noindent Name: \@author \\
	Collaborators: \@collaborators
	\makeatother
\else
\fi

\paragraph{Instructions.}
Solutions must be typeset, with \LaTeX\ strongly preferred. You are encouraged to collaborate on the homework problems with each other in small groups (2-4 people). Collaboration may include brainstorming or exploring possible solutions together on a whiteboard, but should not include one person telling the others how to solve a problem. You must also write up the solutions independently (in your own words) and acknowledge your collaborators at the beginning of the first page.

You may freely use without proof any results proved in class, in Mark's lecture notes posted on the class webpage, or in the main body of the texts assigned as reading. Note that this excludes results that appear in the texts as problems and exercises. You may, of course, use such results but you have to prove them first.


\begin{problem}[Uncertainty principle, O'Donnell 3.15]
	For a function $f : \bits^n \to \R$, define its \emph{Boolean sparsity} to be $\operatorname{sp}(f) = |\operatorname{supp}(f)| = |\{x \mid f(x) \ne 0\}|$. Similarly, define its \emph{Fourier sparsity} by $\operatorname{sp}(\hat{f}) = |\operatorname{supp}(\hat{f})| = |\{S \mid \hat{f}(S) \ne 0\}|$.
	\begin{enumerate}[a)]
		\item Show that for every $S \subseteq [n]$, we have $|\hat{f}(S)| \le \|f\|_1 := \Ex{x}{|f(x)|}$.
		
		\begin{solution}
		%Your solution here
		\end{solution}
	
		\item Show that
		\[\|\hat{f}\|_2^2 := \sum_{S \subseteq [n]} \hat{f}(S)^2 \le \operatorname{sp}(\hat{f}) \cdot \|f\|_1^2.\]
		
		\begin{solution}
			%Your solution here
		\end{solution}
	
		\item Show that
		\[\|f\|_2^2 := \Ex{x \sim \bits^n}{f(x)^2} \ge 2^n \cdot \|f\|_1^2 / \operatorname{sp}(f).\]
		
		\begin{solution}
			%Your solution here
		\end{solution}
	
	
		\item Deduce the ``uncertainty principle'': For every nonzero function $f : \bits^n \to \R$, we have $\operatorname{sp}(f) \cdot \operatorname{sp}(\hat{f}) \ge 2^n$.
		
		\begin{solution}
			%Your solution here
		\end{solution}
	
		\item When is the uncertainty principle tight? Justify your answer.
		
		\begin{solution}
			%Your solution here
		\end{solution}
	\end{enumerate}
\end{problem}


\begin{problem}[Hardness amplification]
	A central topic in average-case complexity is \emph{hardness amplification}: Can a function $f$ that is mildly hard on average, e.g., there is no small circuit that computes $f$ correctly for $99.9\%$ of inputs, be generically transformed into a function $F$ that small circuits cannot predict much better than random guessing, e.g., $50.1\%$? An example of such a result is Yao's XOR lemma, which says that if circuits of size $s$ can compute $f$ with probability at most $1-\delta$, then circuits of size $\lesssim s(1-2\delta)^k$ can compute $\underbrace{f \oplus \dots \oplus f}_{k \text{ times}}$ with probability at most $1/2 + (1-2\delta)^k$.
	
	Noise sensitivity turns out to be an important tool for our understanding of hardness amplification for relatively weak classes like $\NP$. That is, we would like to understand whether mildly hard functions in $\NP$ can be transformed into extremely hard functions that are still in $\NP$. The XOR lemma doesn't help here, since the XOR of two $\NP$ languages is not necessarily also in $\NP$. In this problem, you will fill in some of the details of Healy, Vadhan, and Viola's exposition of Trevisan's proof of O'Donnell's ``Hardness Amplification within $\NP$'' theorem.
	
	\medskip
	
	Let $f : \bits^n \to \bits$ be a $\delta$-hard function, in that for every small circuit $T$, we have $\Pr_x[T(x) = f(x)] \le 1-\delta$. We amplify the hardness of $f$ using functions of the form $(C \circ f^k): (\bits^n)^k \to \bits$ defined by $(C \circ f^k)(x^1, \dots, x^k) = C(f(x^1), \dots, f(x^k))$, where $C : \bits^k \to \bits$ is a combining function. The first step is to reduce the study of the computational hardness of $C \circ f^k$ to the information-theoretic hardness of a related object $C \circ g^k$ where $g$ is a \emph{probabilistic function}.
	
	A probabilistic function is a randomized algorithm $h : \bits^n \to \bits$. It may help to think of $h$ as a function of two inputs: a normal input $x \in \bits^n$ and a random input $r \in R$ for some sample space $R$. So on a fixed input $x$, the expression $\E[h(x)]$ is shorthand for $\Ex{r \sim R}{h(x; r)}$.
	
	For a probabilistic function $h : \bits^n \to \bits$, define
	\[\operatorname{ExpBias}(h) = \Ex{x \sim \bits^n}{\left|\Ex{}{h(x)}\right|}\]
	
	\begin{enumerate}[a)]
	\item Show that the expected bias of a probabilistic function $h$ characterizes the ability of any (even computationally unbounded) device to compute $h$:
		\[\max_{T : \bits^n \to \bits} \Pr[T(x) = h(x)] = \frac{1}{2} + \frac{1}{2} \operatorname{ExpBias}(h).\]
		
		\begin{solution}
			%Your solution here
		\end{solution}
	\end{enumerate}

	\medskip

	If $g$ is a balanced function, i.e., $\Ex{x}{\E[g(x)]} = 0$ and there exists a set $H$ with $|H| = 2\delta \cdot 2^n$ such that a) $g(x)$ is a uniform bit for $x \in H$ and b) $g$ is deterministic for every $x \notin H$, we say that $g$ is \emph{$\delta$-random}. That is, $g$ is (information-theoretically) hard to predict because there is a $2\delta$ fraction of inputs on which it is completely unpredictable.
	
	Your intuition may suggest that if $f$ is mildly hard, the reason may be different for different circuits. That is, the place where circuit $T_1$ errs in computing $f$ may be totally different from the place where circuit $T_2$ errs. Remarkably, Impagliazzo's hardcore lemma says that mildly hard functions ``look like'' $\delta$-random functions to small circuits -- the hardness of every mildly hard function is explained by its being completely unpredictable on a small set of inputs to \emph{every} small circuit. Combining the hardcore lemma with part (a) and a few other ideas, one can show:
	
	\begin{lemma}[Informal] If $f$ is $\delta$-mildly hard for small circuits, then there exists a $\delta$-random function $g$ such that
	\[\Pr[T(x) = (C \circ f^k)(x)] \le \frac{1}{2} + \frac{1}{2}\operatorname{ExpBias}(C \circ g^k)\]
	for every small circuit $T$.\footnote{Note that even if we were careful about what ``small'' means here, statement is not  literally true because of various losses in parameters like $\delta$, the circuit size, and the final upper bound on success probability. But let's pretend it's true to simplify the story.} 
	\end{lemma}
Thus, in order to show that $C\circ f^k$ is extremely hard, it suffices to show that $C \circ g^k$ has small expected bias for every $\delta$-random $g$.
		
	\begin{enumerate}[a)]
		\setcounter{enumi}{1}
	\item	Define the distribution $E_{2\delta}$ over $\bits^k$ as follows. To sample $e \sim E_{2\delta}$, set each $e_i$ independently to $-1$ with probability $2\delta$ and to $+1$ with probability $1-2\delta$. Show that for every $C$ and every $\delta$-random function $g$, \[\operatorname{ExpBias}(C \circ g^k) = \Ex{\substack{y \sim \bits^k \\ e \sim E_{2\delta}}}{\left|\Ex{z \sim \bits^k}{C(y \oplus (e \land z))}\right|}.\]
	The expression looks a bit gnarly, but the following should help to interpret it. To sample the string $y \oplus (e \land z)$, first sample $y \sim \bits^k$ uniformly. Then choose roughly a $2\delta$-fraction of the coordinates specified by $e$, and re-randomize these coordinates according to the string $z$. Note in particular that the pair $(y, y \oplus (e \land z))$ is $(1-2\delta)$-correlated.
	
	\begin{solution}
		%Your solution here
	\end{solution}
	
	\item Show that
	\[\Stab_{1-2\delta}(C) = \Ex{\substack{y \sim \bits^k \\ e \sim E_{2\delta}}}{\Ex{z, w \sim \bits^k}{C(y \oplus (e \land z)) \cdot C(y \oplus (e \land w))}}.\]
	
	\begin{solution}
		%Your solution here
	\end{solution}
	
	\item Combine parts (b) and (c) to conclude that
	\[\operatorname{ExpBias}(C \circ g^k) \le \sqrt{\Stab_{1-2\delta}(C)}.\]
	
	\begin{solution}
		%Your solution here
	\end{solution}

	
	\item The last piece of the puzzle is to exhibit combining functions $C$ that have very low noise stability. The XOR function (parity) is highly noise sensitive, so it has very low noise stability. Use part (d) and Lemma 1 to (qualitatively) conclude Yao's XOR lemma.
	
	\begin{solution}
		%Your solution here
	\end{solution}
	\end{enumerate}
	
As mentioned before, the XOR lemma is not good enough to obtain hardness amplification within $\NP$. To address this problem, we want $C$ to be polynomial-time computable and \emph{monotone}. By composing the Tribes function with a Recursive-Majority-of-3, O'Donnell showed:
	\begin{lemma}
		For every $\delta > 0$ there exists a $k = \poly(1/\delta)$ and a poly-time computable monotone function $C : \bits^k \to \bits$ such that $\Stab_{1-2\delta}(C)\le 1/\poly(k)$.
	\end{lemma}

	\begin{enumerate}[a)]
				\setcounter{enumi}{5}
	\item Combine part (d), Lemma 1, and Lemma 2 to argue that if a family of functions $f_n: \bits^n \to \bits$ is in $\NP$ and $(1/\poly(n))$-hard for small circuits, then there exists a family of functions $F_m : \bits^m \to \bits$ in $\NP$ that cannot be computed with probability better than $1/2 + 1/\poly(m)$ by small circuits.
	
	\begin{solution}
		%Your solution here
	\end{solution}
	\end{enumerate}
\end{problem}

%\begin{problem}[Anticoncentration from hypercontractivity]
%	Let $X$ be a $(2, 4, \rho)$-hypercontractive random variable such that $\|X\|_2 = 1$. For simplicity, you can assume $X$ is finite so all moments exist and you don't have to worry about interchanging limiting operations.
%	\begin{enumerate}[a)]
%		\item Show that $\E[X] = 0$. Hint: For $r \in \{2, 4\}$, compute the first-order Taylor expansion of $\|1 + tX\|_r$ around $t = 0$.
%		\item For $\theta \in \R$, let $Y = (X - \theta)^2$. Show that $\E[Y] = 1 + \theta^2$ and $\E[Y^2] \le (\rho^{-2} + \theta^2)^2$.
%		\item Use the Paley-Zygmund inequality to conclude that
%		\[\Pr[|X - \theta|^2 > t] \ge \left(\frac{\rho^2(1-t^2) + \rho^2\theta^2}{1 + \rho^2\theta^2}\right)^2.\]
%		\item Minimize the right-hand side to conclude the anticoncentration result that for all $\theta \in \R$,
%		\[\Pr[|X - \theta|^2 > t] \ge (1-t^2)^2 \rho.\]
%	\end{enumerate}
%\end{problem}


\begin{problem}[Bonami variant, O'Donnell 9.34]
	Prove the following variant of Bonami's Lemma: For every $f : \bits^n \to \R$,
	\[\E[f(x)^4] \le \operatorname{sp}(\widehat{f}) \cdot \E[f(x)^2]^2.\]
	Thus, not only are low-degree polynomials reasonable, but sparse polynomials are reasonable as well.
\end{problem}


\begin{problem}[Generalizing KKL] \hfill
	\begin{enumerate}[a)]
		\item Let $f : \bits^n \to \bits$ be computed by a decision tree of depth $d$. Show the following improved version of KKL:
		\[\MaxInf[f] \ge \frac{\Var{}{f}}{d}.\]
		\begin{solution}
			%Your solution here
		\end{solution}
		\item Show that the KKL Theorem is false for real-valued functions $f : \bits^n \to [-1, 1]$. (O'Donnell 9.20 -- look there if you need a hint.)
		
		\begin{solution}
			%Your solution here
		\end{solution}
	\end{enumerate}
	A great open problem related to these questions the Aaronson-Ambainis conjecture: For any $f : \bits^n \to [-1, 1]$, we have $\MaxInf[f] \ge \poly(\Var{}{f} / \deg(f))$.
\end{problem}
\end{document}





