Solutions to Homework 4
Problem 1
Part 1
Let $X_i$ be the indicator random variable which is 1 if $h(a_i) < N/4k$. We would like to estimate the expected value of $\sum_i X_i$, i.e., the expected number of hashed values that are less than $N/4k$. By linearity of expectation, we can concentrate on estimating $\mathbb{E}[X_1]$. Since we are dealing with a strongly 2-universal family of hash functions, $\Pr[h(a_1) = \alpha] = 1/N$ for each $\alpha \in {1, \ldots, n}$. (To prove this, use the fact that $\Pr[h(a_1) = \alpha \land h(a_2) = \beta] = 1/N^2$ for every $\beta$, and sum over all $\beta$’s.) Hence
$$ \Pr[X_1 < N/4k] = \sum_{a=1}^{N/4k-1} \frac{1}{N} = \frac{N/4k - 1}{N} \leq \frac{1}{4k} $$
Hence $\mathbb{E}[X_1] = \Pr[X_1 = 1] = \Pr[h(a_1) < N/4k] \leq \frac{1}{4k}$. Hence $\sum_i \mathbb{E}[X_i] \leq k \left( \frac{1}{4k} \right) = \frac{1}{4}$.
By Markov’s inequality,
$$ \Pr[\text{algorithm’s output} > 4k] = \Pr\left[ \sum_i X_i > 0 \right] \leq \mathbb{E}\left[ \sum_i X_i \right] \leq \frac{1}{4} $$
as desired.
Part 2
The expected number of values $h(a_i)$ that are less than $4N/k$ is $4 - k/N$, by the same analysis as above except with $4N/k$ in place of $N/4k$, and using the indicator random variables $Y_i$ instead of $X_i$, where $Y_i$ is 1 iff $h(a_i) < 4N/k$.
Now for the variance. Let $Y = \sum_i Y_i$.
$$ \text{Var}[Y] = \mathbb{E}[Y^2] - (\mathbb{E}[Y])^2 = \sum_{i,j} \mathbb{E}[Y_i Y_j] - \left( 4 - \frac{k}{N} \right)^2 $$
$$ = \sum_{i \neq j} \mathbb{E}[Y_i] \mathbb{E}[Y_j] + \sum_i \mathbb{E}[Y_i] - \left( 4 - \frac{k}{N} \right)^2 $$
$$ = (k^2 - k)\left( \frac{4}{k} \right)^2 + k \left( \frac{4}{k} \right) - \left( 4 - \frac{k}{N} \right)^2 $$
$$ = 16 - \frac{4}{k} + 4 - 16 - \frac{k}{N} = 4 - \frac{4}{k} - \frac{k}{N} \leq 4 $$
Now $\Pr[Y = 0] \leq \Pr[(Y - \mathbb{E}[Y]) \geq 4] \leq \frac{\text{Var}[Y]}{4^2} = \frac{4}{16} = \frac{1}{4}$. The second inequality is Chebyshev’s inequality. Hence
$$ \Pr \left( \text{algorithm’s output} < \frac{k}{4} \right) = \Pr[Y = 0] \leq \frac{1}{4} $$
Part 3
Memory requirement: $O(b + \log n) = O(\log n)$ (by the constraint on $U$), since this is the total space required to store the hash function and the values of the hashes.
Problem 2
Part 1
Let ${u_1, \ldots, u_k }$ be an independent set of size $k$ in $G.$ Then, let $u_i^v$ be the copy of vertex $u_i$ in $G_v.$ I claim that the set ${ u_i^{u_j} },$ where $1 \le i, j \le k$ is an independent set of size $k^2$ the product graph. It is easy to see that this set has size $k^2$, therefore we only need to show that this is an independent set. To see that this set is an independent set, notice that $u_i^{u_j}$ cannot be a neighbor of any other $u_r^{u_s},$ since if $j \ne s$ then there are no edges between $G_{u_j}$ and $G_{u_s},$ which implies that there is no edge between $u_i^{u_j}$ and $u_r^{u_s},$ in particular. If $s = j,$ then $u_i^{u_j}$ and $u_r^{u_s}$ are copies of $u_i$ and $u_r$ in $G_{u_j}$ and therefore they cannot be neighbors, since $u_i$ and $u_r$ were not neighbors in the origin graph. This proves the claim.
Part 2
Let $I$ be the independent set of size $s.$ Let $C = { G_{v_1}, G_{v_2}, \ldots, G_{v_k} }$ be the set of copies of the original graph such that $I \cap C_{v_i} \ne \emptyset.$ Notice that $(v_i, v_j) \in E(G) \Rightarrow$ either $I \cap G_{v_i} = \emptyset$ or $I \cap G_{v_j} = \emptyset,$ since all vertices of $G_{v_i}$ will be neighbors of all vertices of $G_{v_j}.$ Hence, since $I \cap C_{v_i} \ne \emptyset \ \forall G_{v_i} \in C,$ we must have that ${ v_1, v_2, \ldots, v_k}$ is an independent set of the original graph. If $k \ge \sqrt{s},$ we are done. Else, by the pigeonhole principle, we must have that at least one of the $G_{v_i}’$s has at least $\sqrt{s}$ elements, otherwise the total size of $I$ would be $\le k \cdot \max{ G_{v_i} \cap I } < k \sqrt{s} < \sqrt{s} \sqrt{s} = s,$ which is a contradiction. This proves this part.
Part 3
Let $OPT = OPT_1$ be the optimum for our original problem (with graph $G$), and let $OPT_k$ be the optimum for the problem where the input is the resulting graph $G_k$ when we take $k$ recursive products ($G_k = G_{k-1} \times G_{k-1}$). That is, $OPT_2$ is the optimum of the product graph $G \times G,$ $OPT_3$ is the optimum of the product graph $(G \times G) \times (G \times G),$ and so on. (we will use $G \times G$ to represent the product graph as described in the beginning of the problem.)
Then, by part (a) we know that $OPT_{k-1}^2 \le OPT_k, \ \forall k.$ Now, given an $\alpha$-approximation algorithm for $MIS,$ if we apply it to the product graph $G_k,$ we will get an independent set of size $\ge \frac{OPT_k}{\alpha}.$ Then, by part (b) this means that we can find an independent set in $G_{k-1}$ of size $\ge \sqrt{\frac{OPT_k}{\alpha}} \ge \frac{OPT_{k-1}}{\sqrt{\alpha}}.$ By induction, one can easily see that by starting from $G_k,$ we can find an independent set of $G$ of size $\ge \frac{OPT}{\alpha^{1/2^{k-1}}}$
Hence, if $A$ is our $\alpha$-approximation algorithm for $MIS,$ the family of algorithms ${ A_k },$ where $A_k$ is defined by running $A$ in the product graph $G_k$ and then finding the independent set in the original graph by cascading as we saw above, is a polynomial approximation scheme, since each of the $A_k$’s is polynomial, and for each $\epsilon$ we can set $A_{\epsilon} = A_k,$ where $k$ is the least positive integer such that $\alpha^{1/2^{k-1}} \le 1 + \epsilon.$
The previous paragraph proves that for any $\epsilon > 0$ we can find a $(1+\epsilon)$-approximation algorithm for MIS. This implies that $MIS$ is not MAX-SNP-hard, since for each constant $c > 1,$ there is an $\epsilon > 0$ such that $1 + \epsilon \le c,$ and therefore by using $A_{\epsilon}$ from above we would have that we can get a $c$-approximation to MIS. This contradicts the assumption that MIS is MAX-SNP-hard. Therefore, our initial assumption was wrong and hence there is no $\alpha$-approximation for MIS, for any constant $\alpha.$ This finishes this part.
Problem 3
In class we showed that $\omega_{inv} = \omega_{mult} = \omega$ and also that $\omega_{det} \geq \omega_{inv}$ so now all that is left to show is $\omega_{det} \leq \omega$, that is, any algorithm to invert a matrix can be turned into an algorithm to compute the determinant.
From class, we learned how to get the Schur complement, and that if $$M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$$ where $M \in \mathbb{Q}^{N \times N}$ and $A, B, C, D \in \mathbb{Q}^{N/2 \times N/2}$ then $$ \det(M) = \det(D) \cdot \det(A - BD^{-1}C) $$ Thus, if we denote by $T(N) := $ # operations to compute the determinant of an $N \times N$ matrix we have $$T(N) \leq 2 T(N/2) + 3C(N/2)^\omega + N^2$$ where the term $3C(N/2)^\omega$ accounts for 2 multiplications and one matrix inversion, and the $N^2$ term accounts for one matrix addition.
Since $\omega \geq 2$, by the master’s theorem we have that $T(N) = O(N^\omega)$.
Problem 4
Part 1
Protocol: send your input value to all other processors. Upon receiving everyone’s input values, return the minimum value that you have seen.
Correctness: since there are only clean crashes, all alive processors will receive the same set of messages, and thus will have the same value for the minimum.
Validity and Termination are trivial.
Part 2
Note that if processor $p_a$ was alive at the beginning of the second round, then all alive processors $p_i$ have $x_a \in V_i^{(k)}$ for $k \geq 1$. This is true since $p_a$ will successfully send its message to all other processors in the first round. Hence, $V_i^{(1)} \neq V_j^{(1)}$ for two alive processors iff there is a crash in the first round (and the crashed processor only sent a message to one of $p_i, p_j$). Generalizing this argument we have that $V_i^{(k)} \neq V_j^{(k)}$ for two alive processors iff there are at least $k$ crashes. This proves the lemma.