[ps5] Solutions

1 files changed, 337 insertions, 0 deletions

diff --git a/ps5/main.tex b/ps5/main.tex
new file mode 100644
index 0000000..27c0135
--- /dev/null
+++ b/ps5/main.tex
@@ -0,0 +1,337 @@
+\documentclass[10pt]{article}
+\usepackage{fullpage}
+\usepackage[utf8x]{inputenc}
+\usepackage{amsmath,amsfonts,amsthm}
+\usepackage[english]{babel}
+\usepackage[capitalize, noabbrev]{cleveref}
+\usepackage{algorithm}
+\usepackage{algpseudocode}
+
+\newenvironment{enumerate*}%
+  {\vspace{-2ex} \begin{enumerate} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{enumerate}}
+ 
+\newenvironment{itemize*}%
+  {\vspace{-2ex} \begin{itemize} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{itemize}}
+ 
+\newenvironment{description*}%
+  {\vspace{-2ex} \begin{description} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{description}}
+
+
+\DeclareMathOperator{\E}{\mathbb{E}}
+\DeclareMathOperator{\Enc}{\mathrm{Enc}}
+\DeclareMathOperator{\Dec}{\mathrm{Dec}}
+\DeclareMathOperator{\Ext}{\mathrm{Ext}}
+\let\P\relax
+\DeclareMathOperator{\P}{\mathbb{P}}
+\DeclareMathOperator*{\argmin}{\arg\min}
+\newcommand{\ex}[1]{\E\left[#1\right]}
+\newcommand{\prob}[1]{\P\left[#1\right]}
+\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
+\newcommand{\R}{\mathbf{R}}
+\newcommand{\poly}{\text{poly}}
+\newcommand{\N}{\mathbf{N}}
+\newcommand{\C}{\mathcal{C}}
+\newcommand{\eps}{\varepsilon}
+\newcommand{\cl}[1]{\text{\textbf{#1}}}
+\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
+\newcommand{\llbracket}{[\![}
+
+
+\newtheorem{theorem}{Theorem}
+\newtheorem{lemma}{Lemma}
+\algrenewcommand\algorithmicensure{\textbf{Output:}}
+\algrenewcommand\algorithmicrequire{\textbf{Input:}}
+
+\author{Thibaut Horel}
+\title{CS 225 Problem Set 5 -- Solutions}
+
+\begin{document}
+\maketitle
+
+\section*{Problem 6.1}
+
+\paragraph{1.}
+Let us denote by $\mathcal{U}$ the universe on which $X$ and $Y$
+are defined, and define $p_X(i) = \P[X=i]$ for $i\in \mathcal{U}$ (and
+similarly for $Y$). Let us partition $\mathcal{U} = S_X\cup S_Y$ where $S_X
+= \{i\in\mathcal{U}, p_X(i) > p_Y(i)\}$ (and $S_Y$ is the complement of $S_X$).
+
+For a $[0,1]$ valued function $f$ defined over $\mathcal{U}$, we have:
+\begin{displaymath}
+    \big | \E[f(X)] - \E[f(Y)]\big|
+    = \left|\sum_{i\in S_X} \big(p_X(i) - p_Y(i)\big) f(i)
+    + \sum_{i\in S_Y} \big(p_X(i) - p_Y(i)\big) f(i)\right|
+\end{displaymath}
+notice that the terms in the first sum are positive and the terms in the second
+sum are negative. Hence, if we want to maximize the above expression over all
+$f$s, we should either set $f(i) = 1$ for all $i\in S_X$ and $0$ elsewhere, or
+vice versa. In the first case we would obtain a value:
+\begin{displaymath}
+    V_1\eqdef \sum_{i\in S_X} \big(p_X(i) - p_Y(i)\big)
+\end{displaymath}
+in the second case:
+\begin{displaymath}
+    V_2\eqdef \sum_{i\in S_Y} \big(p_Y(i) - p_X(i)\big)
+\end{displaymath}
+Using that $p_X$ and $p_Y$ are probability distributions, we observe that
+$V_1 = V_2$ (indeed, this is equivalent to $1=1$ after re-ordering the terms).
+Hence:
+\begin{equation}\label{eq:foo}
+    \max_f\big | \E[f(X)] - \E[f(Y)]\big| = 
+    \sum_{i\in S_X} \big(p_X(i) - p_Y(i)\big)=
+    \sum_{i\in S_Y} \big(p_Y(i) - p_X(i)\big)
+\end{equation}
+
+We have now showed:
+\begin{displaymath}
+    \Delta(X, Y) = \max_f\big | \E[f(X)] - \E[f(Y)]\big|
+\end{displaymath}
+Indeed, we clearly have $\Delta(X, Y) \leq \max_f\big | \E[f(X)]
+- \E[f(Y)]\big|$, since $\Delta(X, Y)$ is the specific case where $f$ is
+a $\{0,1\}$-function, but the proof above shows that the inequality is in fact
+an equality since the maximum for $f$ is reached for a $\{0,1\}$-function.
+
+Finally, we observe that:
+\begin{displaymath}
+    \frac{1}{2}|X-Y|_1 = \frac{1}{2}\sum_{i\in\mathcal{U}}|p_X(i)-p_Y(i)|
+    =\frac{1}{2}\sum_{i\in S_X}\big(p_X(i)-p_Y(i)\big)
+    + \frac{1}{2}\sum_{i\in S_Y}\big(p_Y(i)-p_X(i)\big)
+    =\frac{V_1}{2}+\frac{V_2}{2}
+\end{displaymath}
+Using \eqref{eq:foo}, this implies:
+\begin{displaymath}
+    \frac{1}{2}|X-Y|_1 = \max_f\big | \E[f(X)] - \E[f(Y)]\big|
+\end{displaymath}
+and concludes the proof of this part.
+
+\paragraph{2.} Let us consider a $w$ such that $X_w \eqdef X|_{W=w}$ is not
+a $k-l-\log\frac{1}{\eps}$ source. Then this implies that there exists an $x$
+such that:
+\begin{displaymath}
+    \P[X_w=x]>\frac{1}{2^{k-l-\log\frac{1}{\eps}}}
+\end{displaymath}
+But we have:
+\begin{displaymath}
+    \P[X_w=x] = \frac{\P[X=x\wedge W=w]}{\P[W=w]}\leq
+    \frac{1}{2^k}\frac{1}{\P[W=w]}
+\end{displaymath}
+where the inequality uses that $(W,X)$ is a $k$ source. The above two
+inequalities together imply:
+\begin{displaymath}
+    \P[W=w]\leq \frac{\eps}{2^l}
+\end{displaymath}
+Denoting by $B$ the $w$s such that $X_w$ is not a $k-l-\log\frac{1}{\eps}$
+source, we obtain:
+\begin{displaymath}
+    \P[W\in B] = \sum_{w\in B}\P[W=w]\leq |B|\frac{\eps}{2^l}\leq \eps
+\end{displaymath}
+since $|B|\leq 2^l$. This concludes the proof.
+
+\paragraph{3.} This is a consequence of \textbf{2.}. Let us denote by $B$ the
+set of $x_1\in\{0,1\}^{n_1}$ such that $X_2|_{X_1=x_1}$ is not
+a $n_2-\Delta-\log\frac{1}{\eps}$ source. Define $X_2'$ to be the following
+variable:
+\begin{displaymath}
+    X_2' = \begin{cases}
+        U_{n_2}&\text{if $X_1\in B$}\\
+        X_2&\text{otherwise}
+    \end{cases}
+\end{displaymath}
+$X_1$ is a $n_1-\Delta$ source. Indeed:
+\begin{displaymath}
+    \P[X_1=x_1] = \sum_{x_2} \P[X_1=x_1\wedge X_2 = x_2]\leq
+    2^{n_2}\frac{1}{2^{n-\Delta}} = \frac{1}{2^{n_1-\Delta}}
+\end{displaymath}
+where the inequality used that $X$ is a $n-\Delta$ source. For all $x_1$,
+$X_2'|_{X_1=x_1}$ is a $n_2-\Delta-\log\frac{1}{\eps}$ source: either $x_1\notin
+B$ and this is by definition, or $x_1\in B$ and then $X_2'|_{X_1=x_i}$ is
+uniform, i.e a $n_2$ source). Hence, $(X_1,X_2')$ is a $(n_1-\Delta,
+n_2-\Delta-\log\frac{1}{\eps})$ block source. Finally:
+\begin{displaymath}
+    \Delta\big((X_1,X_2),(X_1,X_2')\big) \leq \P[X_1\in B]\leq \eps
+\end{displaymath}
+where the last inequality used \textbf{2.}. $(X_1,X_2')$ satisfies all
+the requirements.
+
+\section*{Problem 6.5}
+
+\paragraph{1.} I use the expander walk averaging sampler of Theorem 4.23. This
+sampler uses $m+ \frac{C_1}{\eps^2}\log\frac{1}{\delta\eps}$ random bits for an
+output of length $m$ and uses $\frac{C_2}{\eps^2}\log\frac{1}{\delta}$ samples.
+
+By Corollary 6.24, this implies a $(k, \eps)$ extractor for $k=
+n+\log\delta+\log\frac{1}{\eps}$.
+
+We want seed length $d\leq \log n$. Hence we have to set $\delta$ high enough
+such that:
+\begin{displaymath}
+    \log\frac{1}{\delta}\leq \frac{n\eps^2}{C_2}
+\end{displaymath}
+
+We want $m\geq (1-\alpha)n$. This is equivalent to:
+\begin{displaymath}
+    \alpha m\geq (1-\alpha)\frac{C_1}{\eps^2}\log\frac{1}{\delta\eps}
+\end{displaymath}
+again, this can be achieved by setting $\delta$ high enough (we will have to
+take $\delta$ to be the max of this value and the value obtained above).
+
+Finally we need to verify that $k$ is $\beta n$ for some $\beta<1$. But we have:
+\begin{displaymath}
+    k = n + \log \delta + \log\frac{1}{\eps} \geq n -\frac{n\eps^2}{C_2}
+    = n(1-\eps^2/C_2)
+\end{displaymath}
+which concludes the proof.
+
+\paragraph{3.} Using Corollary 6.24, the extractor of Theorem 6.36 implies the
+existence of a $(K/B,\eps)$ averaging sampler using $b$ random bits and
+$\text{poly}(b/\eps)$ samples provided that $k\leq 2m$ (where $m$ is the bit
+length of the samples).
+
+Assuming w.l.o.g. that the success probability of the algorithm $A$ for our
+$\cl{BPP}$ problem is $\frac{2}{3}$, choosing $\eps=\frac{1}{6}$ and
+$K/B=\frac{1}{2^l}$ and averaging the output of $A$ on all $\text{poly}(b)$
+samples of the sampler (we fix the input $x$ of $A$ and use the samples as
+random bits), the error probability is now at most $\frac{1}{2^l}$.
+
+We need to set $m = r$. Setting $k = 2m$, this implies $b = k + l = O(r) + l$.
+The number of samples used is $\text{poly}(b) = \text{poly}(r, l)$. Since $r$
+and $l$ are polynomial in $n$, the resulting algorithm is still polynomial in
+$n$.
+
+\paragraph{} Starting from an algorithm $A$ with probability of success $2/3$
+and using $r = r(n)$ random bits, the first part of this question shows that
+using $q = Cr +l$ random bits (for some constant $C$) implies an error
+probability of $2^{-l}$. Setting $l = (Cr)^{100}$, we have $2^{-l}2^q
+= 2^{Cr}\leq 2^{q^{0.01}}$, i.e, the algorithm errs on at most $2^q^{0.01}$
+choices of its $q$ random bits. The running time is still polynomial since $l$
+is polynomial in $r$.
+
+\section*{Problem 6.9}
+
+We first condense the source using Theorem 6.34, yielding a source of length
+$(1+\alpha)k +O(\log \frac{n}{\eps_1})$ which is $\eps_1$ close to
+a $k+O(\log\frac{n}{\eps_1})$ source using a seed of length $O(\log
+\frac{n}{\eps_1})$. We will set $\eps_1$ and $\alpha$ later.
+
+We now partition the condensed source in $t$ blocks of size $k/t
++ O(\log\frac{n}{\eps_1})$ (from now on, the $O$ will hide $t$ terms, but we do
+not care since $t$ is constant). Applying Lemma 6.31 $t$ times (we proved it in
+Problem 6.1), the resulting source is $\eps_1 + t\eps_1$ close to a $t\times
+k_1$ source, with:
+\begin{displaymath}
+    k_1 = \frac{1+\alpha}{t}k - \alpha k + O\left(\log \frac{n}{\eps_1}\right)
+\end{displaymath}
+note that for this to work, we will need $\alpha < \frac{1}{t}$, this will be
+satisfied when we set $\alpha$ later.
+
+Using Theorem 6.18, we know that there exists an extractor with seed length $n$
+(for input length $n$) which is a $(k, \eps)$ extractor with $m
+= k + n - O(\log\frac{1}{\eps})$.
+
+We use this extractor in Lemma 6.28 to do block extraction on the block source
+constructed above (using the same extractor for each block). The number of
+random bits we need for this is $\frac{k}{t} + O(\log \frac{n}{\eps_1})$. The
+number of extracted bits is:
+\begin{displaymath}
+    m = t\times\big(k_1 - \log\frac{1}{\eps_1}\big)\geq k-\alpha
+    k t + O\left(\log\frac{n}{\eps_1}\right)
+\end{displaymath}
+If we choose $\alpha = \frac{1}{2t}$, we will have $m\geq \frac{k}{2}$ as
+required (this also implies $\alpha< \frac{1}{t}$ as was needed above).
+
+The resulting source will be $\eps_1 + t\eps_1 + t\eps_1$ close to a uniform
+source. This implies that we need to set $\eps_1 = \frac{\eps}{1+2t}$.
+
+Finally the number of bits needed is $O(\log\frac{n}{\eps_1})$ for the
+condenser, and $\frac{k}{t} + O(\log\frac{n}{\eps_1})$ to bootstrap the block
+extraction. Given our choice of $\eps_1$, this is $\frac{k}{t}
++ O(\log\frac{n}{\eps})$ as required.
+
+\section*{Problem 6.10}
+
+\paragraph{1.} I define the following encryption scheme with $n=m=l$:
+\begin{displaymath}
+    \Enc(k, u) = \Ext(k)\oplus u,\quad
+    \Dec(k, e) = \Ext(k)\oplus e
+\end{displaymath}
+It is clear that for any message $u$, we have $\Dec(k, \Enc(k, u)) = k$.
+Furthermore, by definition of $\Ext$, for any $K\in\mathcal{C}$, $\Ext(K)$ is
+$\eps$ close to uniform over $\{0,1\}^m$, hence for any pair of messages
+$(u,v)$:
+\begin{align*}
+    \Delta(\Enc(K,u),\Enc(K,v)) &= \Delta(\Ext(K)\oplus u, \Ext(K)\oplus v)
+    \leq \Delta(\Ext(K)\oplus u, U_m) + \Delta(\Ext(K)\oplus v, U_m)\\
+    &\leq \Delta(\Ext(K), U_m\oplus u) + \Delta(\Ext(K), U_m\oplus v)\leq 2\eps
+\end{align*}
+Where we used the triangle inequality (and the fact that $\Delta$ can only
+decrease by applying the same function to both its arguments) and that
+$U_m\oplus u$ is still uniform for any $u$.
+
+\paragraph{2. (a)} I use the probabilistic method similarly to the proof of
+Proposition 6.12 (there might be a way to reduce to it directly, but I haven't
+found how). Define $m'
+= m - 2\log\frac{1}{\eps} - c_1$ (for some constant $c_1$), and consider a totally random function $f$
+\begin{displaymath}
+    \P[f\text{ is not an $\eps$-extractor}] = \P_f[\exists (k, T) \text{ s.t.}
+    \P_{U_m}[f(\Enc(k,U_m)\in T] - \P_{U_{m'}}[U_m'\in T]>\eps]
+\end{displaymath}
+We fix $k$ and $T$ (and we will union bound later). We have:
+\begin{displaymath}
+    \P_f[\P_{U_m}[f(\Enc(k,U_m)\in T] - \P_{U_{m'}}[U_m'\in T]>\eps] =
+    \P_f[\P_{U_m}[f(\Enc(k,U_m)\in T]-\mu>\eps]
+\end{displaymath}
+where I defined $\mu = \frac{T}{2^{m'}}$. For fixed $u\in\{0,1\}^m$,
+$f(\Enc(k, u))$ is a uniform variable over $\{0,1\}^{m'}$ (since $f$ is
+totally random), hence:
+\begin{displaymath}
+    \P_f[\P_{U_m}[f(\Enc(k,U_m)\in T]-\mu>\eps]
+    = \P\left[\frac{1}{2^m}\sum_{u\in\{0,1\}^m} Y_u - \mu>\eps\right]
+\end{displaymath}
+where the $Y_u$ are independent Bernouilli variables of parameter $\mu$. Using
+the Chernoff bound, we get that the above probability is bounded by
+$\exp(-2^m\eps^2/4)$. Taking a union bound over $k$ and $T$, the probability
+that $f$ is not an $\eps$-extractor is bounded above by
+$2^{m'}2^n\exp(-2^m\eps^2/4)$.
+
+Using that $m' = m - 2\log \frac{1}{\eps} - c_1$, we can upper bound the
+probability $p$ computed above:
+\begin{displaymath}
+    p\eqdef 2^{m'}2^n\exp(-2^m\eps^2/4)
+    = \frac{2^m\eps^2}{c_2}2^n\exp(-2^m\eps^2/4)
+\end{displaymath}
+where $c_2= 2^{c_1}$. Using $x\leq e^x$, we  have:
+\begin{displaymath}
+    p\leq \exp(n\log 2 - 2^m\eps^2(\frac{1}{c_2}-\frac{1}{4}))
+\end{displaymath}
+Finally, using that $2^m\geq c_3\frac{n}{\eps^2}$, it is clear that we can find
+a setting of the constants such that the argument of the $\exp$ function is
+negative, i.e $p<1$. This implies the existence of a function $f$ which is
+a deterministic $\eps$-extractor.
+
+\paragraph{2. (b)} Still denoting by $m'$ the output length of $\Ext'$, we want
+to upper bound, for $K\in\mathcal{C}$:
+\begin{align*}
+    \Delta(\Ext'(\Enc(K, 0^m)), U_{m'})&\leq
+    \Delta(\Ext'(\Enc(K, 0^m)), \Ext'(\Enc(K, U_m)))
+    + \Delta(\Ext'(\Enc(K, U_m)), U_{m'})\\
+    &\leq \eps +\Delta(\Ext'(\Enc(K, U_m)), U_{m'})\\
+    &\leq 2\eps
+\end{align*}
+where the first inequality used the triangle inequality, the second inequality
+averages on the different taken by $U_m$ in the first term: for all $u\in\{0,1\}^m$:
+\begin{displaymath}
+\Delta(\Ext'(\Enc(K, 0^m)), \Ext'(\Enc(K, u)))
+\leq \Delta(\Enc(K, 0^m), \Enc(K, u))\leq \eps
+\end{displaymath}
+using that $\Enc$ is $\eps$-secure. Finally, the last inequality averages on
+the different values $k$  taken by $K$ in the second term: for each $k$ the
+term is smaller than $\eps$ using that $\Ext'$ is an $\eps$-extractor. This is
+still true after averaging over all values taken by $K$.
+
+\end{document}