From be1c547251f197fb04feade8c296d0dc1877bed8 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 20 Apr 2015 00:16:56 -0400 Subject: [ps5] Solutions --- ps5/main.tex | 337 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 337 insertions(+) create mode 100644 ps5/main.tex 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} -- cgit v1.2.3-70-g09d2