diff options
| -rw-r--r-- | ps2/main.tex | 184 |
1 files 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} |