From 8306269baf96c194b708d6eb28db91b1d4ee0daf Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sat, 28 Feb 2015 15:22:47 -0500
Subject: [ps2] second and third problems

---
 ps2/main.tex | 184 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 181 insertions(+), 3 deletions(-)

diff --git a/ps2/main.tex b/ps2/main.tex
index ecfba0b..d628770 100644
--- a/ps2/main.tex
+++ b/ps2/main.tex
@@ -25,10 +25,12 @@
 \DeclareMathOperator{\E}{\mathbb{E}}
 \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}
@@ -213,13 +215,189 @@ value at most:
 where we used $\sqrt{1-x}\leq 1-\frac{x}{2}$ which concludes the question by
 definition of $\lambda(G)$.
 
-\paragraph{6.} The analysis we did in \textbf{4.} used that the length of
-a path from $i^*$ to $k$ had length $l\leq n$. If we know the diameter $D$, we
-have $l\leq D$. The same analysis gives $\lambda_2\leq 1- \frac{1}{dDn}$.
+\paragraph{6.} The analysis we did in \textbf{4.} used that a path from
+$i^*$ to $k$ had length $l\leq n$. If we know the diameter $D$, we have $l\leq
+D$. The same analysis gives $\lambda_2\leq 1- \frac{1}{dDn}$.
 
 Finally, \textbf{5.} implies that $\gamma(G) \geq \frac{1}{2d^2n^2}$.
 
 \section*{Problem 3.1}
 
+Let us consider a problem $(Y, N)$ in $\cl{prBPP}$ where $Y$ (resp. $N$) is
+the set of “yes” (resp. “no”) instances. There is a polynomial time algorithm
+$A$ such that for all $x$, $\prob{ A(x) \text{ correct}}\geq 1-\frac{1}{2^n}$.
+The algorithm uses $m = poly(n)$ coin tosses. For input $x$, let us denote by
+$A_x$ the set of coin tosses $r$ such that $A(x; r)$ says “yes”.
+Using exactly the same analysis as in the proof of Theorem 3.14, we can prove:
+\begin{itemize}
+    \item $x\in Y \implies \P_s\big[\forall r\in \{0,1\}^m,\; P(x,s,r) = 1\big]
+        > 1 - \frac{2^m}{2^{nm}}$ where $s$ is a $m$-tuple of random bits.
+    \item $x\in N \implies \forall s\in\{0,1\}^m,\; \P_r\big[P(x,s,r)
+        = 1\big]<\frac{m}{2^{n}}$ were $r$ is a $m$-tuple of random bits.
+\end{itemize}
+for $P(x,s,r) = \bigvee_{i=1}^m \big(A(x;r\oplus s_i) = 1\big)$. Clearly $P$
+can be computed in polynomial time.
+If we define:
+\begin{itemize}
+    \item $Y' = \big\{(x,s):\, \forall r\in\{0,1\}^m,\; P(x,s,r) = 1\big\}$
+    \item $N' = \big\{(x,s):\, \P_r[ P(x,s,r) = 1]<\frac{m}{2^n}\big\}$
+\end{itemize}
+then $(Y', N')$ is clearly in $\cl{prco-RP}$ (for input $(x,s)$ take $r$ at
+random and output $P(x,s,r)$). Since we are assuming $\cl{prRP} = \cl{prP}$,
+then $\cl{prco-RP} = \cl{prco-P} = \cl{prP}$. Hence there exists $Q$,
+a polynomial time predicate such that:
+\begin{itemize}
+    \item $x\in Y \implies \P_s\big[Q(x,s) = 1\big]
+        > 1-  \frac{2^m}{2^{nm}}$ where $s$ is a $m$-tuple of random bits.
+    \item $x\in N \implies \forall s\in\{0,1\}^m,\; Q(x,s) = 0$.
+\end{itemize}
+But now we see that:
+\begin{itemize}
+    \item $Y'' = \{x:\, \P_s[Q(x,s) = 1]>1-\frac{2^m}{2^{nm}}\}$
+    \item $N'' = \{x:\, \forall s,\; Q(x,s) = 0\}$
+\end{itemize}
+is in $\cl{prRP} = \cl{prP}$. Hence there is a polynomial time predicate $R$
+such that:
+\begin{itemize}
+    \item $x\in Y\implies R(x) = 1$
+    \item $x\in N\implies R(x) = 0$
+\end{itemize}
+which proves that $(Y,N)$ is in $\cl{prP}$. This implies that $\cl{prBPP}
+= \cl{prP}$ and thus that $\cl{BPP} = \cl{P}$.
+
 \section*{Problem 3.2}
+
+\paragraph{1.} Let us assume that $S_1,\ldots,S_{i-1}$ have already been
+constructed and satisfy the $(l,a)$ design requirements. Then, for $S_i$ chosen
+uniformly at random in $[d]$, we have:
+\begin{displaymath}
+    \E_{S_i}\big[\#\{j<i : |S_i\cap S_j|\geq a\}\big]
+    = \sum_{j=1}^{i-1}\P_{S_i}[|S_i\cap S_j|\geq a]
+\end{displaymath}
+For a fixed $j$, we see that:
+\begin{displaymath}
+    \P_{S_i}[|S_i\cap S_j|\geq a]\leq
+    \frac{{l \choose a}{d-a\choose l-a}}{{d\choose l}}
+    =\frac{{l\choose a}^2}{{d\choose a}}
+\end{displaymath}
+the inequality is simple combinatorics: for $S_i$ to overlap with $S_j$ by more
+than $a$ elements, we first pick a subset of $a$ elements in $S_j$, and then
+$l-a$ elements among the remaining elements. The equality uses the definition
+of the binomial coefficient and basic algebra.
+
+Summing over $m$ and using the assumed bound on $m$ we directly obtain:
+\begin{displaymath}
+    \E_{S_i}\big[\#\{j<i : |S_i\cap S_j|\geq a\}\big] < 1
+\end{displaymath}
+
+\paragraph{2.} We can rewrite the result obtained in \textbf{1.} as, for all
+$S_1,\ldots, S_{i-1}$:
+\begin{equation}
+    \label{eq:foo}
+    \exists S_i\in[d],\; \forall j<i,\; |S_i\cap S_j|< a
+\end{equation}
+otherwise we would have:
+\begin{displaymath}
+    \forall S_i\in[d],\; \#\{j<i : |S_i\cap S_j|\geq a\}\geq 1
+\end{displaymath}
+and integrating over uniformly random subset $S_i$ would contradict
+\textbf{1.}.
+
+Equation~\eqref{eq:foo} shows that we will be able to construct an $(l,a)$
+design: for $i\in\{1,\ldots,m\}$, we are always guaranteed that there exists
+a set $S_i$ of size $l$ which does not overlap by more than $a$ with any of the
+previously selected sets. We now need to control the sizes of the different
+parameters.
+
+For fixed $(l,m)$ and $a = \gamma\log m$ for some $\gamma > 0$, we need:
+\begin{displaymath}
+    m\leq {d\choose a}/{l \choose a}^2
+\end{displaymath}
+we use the standard inequalities:
+\begin{displaymath}
+    \left(\frac{n}{k}\right)^k\leq
+    {n\choose k} \leq \left(\frac{ne}{k}\right)^k
+\end{displaymath}
+to prove that the condition will be satisfied if:
+\begin{displaymath}
+    \left(\frac{de}{a}\right)^a\geq m\left(\frac{l}{a}\right)^{2a}
+\end{displaymath}
+This is equivalent to:
+\begin{displaymath}
+    d\geq \frac{1}{e}m^{1/a} \frac{l^2}{a}
+    = \frac{2^{1/\gamma}}{e}\frac{l^2}{a} = O\left(\frac{l^2}{a}\right)
+\end{displaymath}
+where the first equality used that $a =\gamma \log m$.
+
+\paragraph{3.} We are going to construct the sets $S_1,\dots, S_{m}$ one by
+one, and for each $i$, we are going to construct $S_i$ element by element using
+the Method of Conditional Expectation. If all the parameters are as in
+\textbf{2.}, we know from \textbf{1.} that if $S_1,\dots,S_{i-1}$ have already
+been constructed, then:
+\begin{displaymath}
+    \E_{S_i}\left[\#\{j<i : |S_i\cap S_j|\geq a\}\right]<1
+\end{displaymath}
+
+For concision, let use write $\phi(S_i) = \#\{j<i : |S_i\cap S_j|\geq a\}$
+where $S_i$ is a uniformly random subset of $[d]$ of size $l$ and
+denote by $S_i^k$ the set constructed after $k$ steps, then we have:
+\begin{displaymath}
+    \E_{S_i}\left[\phi(S_i)\,|\, S_i^k\subseteq S_i\right] = 
+    \E_{e\in [d]\setminus S_i^k}\left[\E_{S_i}\left[\phi(S_i)\,|\,
+    S_i^k\cup\{e\}\subseteq S_i\right]\right]
+\end{displaymath}
+where $e$ is chosen uniformly at random in $[d]\setminus S_i^k$.  Hence, there
+exists $e\in[d]\setminus S_i^k$ such that if we define $S_i^{k+1}=
+S_i^k\cup\{e\}$:
+\begin{displaymath}
+    \E_{S_i}\left[\phi(S_i)\,|\, S_i^k\subseteq S_i\right] \geq
+\E_{S_i}\left[\phi(S_i)\,|\, S_i^{k+1}\subseteq S_i\right]
+\end{displaymath}
+one $e$ which satisfies this property is for example:
+\begin{equation}
+    \label{eq:foo2}
+    e^*\in\argmin_{e\in [d]\setminus S_i^k}\E_{S_i}\left[\phi(S_i)\,|\,
+    S_i^k\cup\{e\}\subseteq S_i\right]
+\end{equation}
+
+Hence for $S_i^k$  constructed by repeatedly adding the element $e^*$ as
+defined in \eqref{eq:foo2}, we are guaranteed:
+\begin{displaymath}
+    \forall k,\;\E_{S_i}\left[\phi(S_i)\,|\, S_i^k\subseteq S_i\right] \leq
+\E_{S_i}\left[\phi(S_i)\right]< 1
+\end{displaymath}
+And in particular for $k=l$, $S_i$ is entirely determined and we have
+$\phi(S_i) = 0$ (since it is an integer). That is, $S_i$ is a valid set to add
+to our design.
+
+The only thing left to show is that computing the design can be done in
+polynomial time. Denoting by $T$ the running time of computing the
+objective function in \eqref{eq:foo2}, constructing the design will take time
+$O(mldT) = O(T\poly(m,d))$, since $d = O(l^2/a)$ and $a = \gamma\log m$.
+
+
+The objective function in \eqref{eq:foo2} can be
+rewritten:
+\begin{displaymath}
+    f_k(e) \eqdef \sum_{j=1}^{i-1}\P_S\left[|(S\cup S_i^k\cup\{e\})\cap
+    S_j|\geq a\right]
+\end{displaymath}
+where $S$ is a uniformly random subset of $[d]\setminus S_i^k\cup\{e\}$ of size
+$l - k-1$.
+
+But as in \textbf{1.}, we can compute $\P_S\left[|(S\cup S_i^k\cup\{e\})\cap
+S_j|\geq a\right]$ using combinatorics. Writing $x_e = |S_i^k\cup\{e\}\cap
+S_j|$:
+\begin{displaymath}
+\P_S\left[|(S\cup S_i^k\cup\{e\})\cap S_j|\geq a\right]
+= \frac{{l-x_e\choose a - x_e}{d - k - 1 - a + x_e\choose l - a + x_e}}{{d - k -1\choose l-k-1}} 
+\end{displaymath}
+Hence $f_k(e)$ which can be computed in time $T = poly(m, l, a, d) = poly(m,d)$
+since $a = \gamma\log m$ and $d = O(l^2/a)$. 
+
+Note that for a practical implementation, using standard recursive identities
+for binomial coefficients, the computation of the objective function can be
+made quite efficient: the value of $f_k(e)$ can be computed in $O(1)$
+arithmetic operations from $f_{k-1}(e)$.
+
 \end{document}
-- 
cgit v1.2.3-70-g09d2