Homework 4

This homework covers the material from lectures 19 to 23.

Due date: July 15th, 10pm Waterloo time.

PDF version of Homework 4.

LaTeX template, in case you want to write it in LaTeX.

Required Exercises

Problem 1 - Distinct Elements (25 points)

Consider again the distinct elements problem that we saw in class. We are given a stream of elements $a_1, \ldots, a_n$ from our universe $U = \{ 0, 1, \ldots, 2^b -1 \}$, possibly with repetitions, and we would like to know how many distinct elements are there in the sequence. Since we are in the streaming setting, we will make only one pass through the sequence above, and we have little memory.

We will now analyze a different algorithm for the distinct elements problem:

• Let $N > n$ be an integer
• Pick at random a function $h : U \rightarrow [N]$ from a strongly 2-universal family.
• Let $m := \min \{ h(a_1), \ldots, h(a_n) \}$
• Output $N/m$

1. Suppose that $a_1, \ldots, a_n$ contains $k$ distinct elements. Show that $$ \Pr[ \text{ algorithm outputs a number } > 4k ] \leq \dfrac{1}{4} $$
2. Suppose that $a_1, \ldots, a_n$ contains $k$ distinct elements. Show that $$ \Pr[ \text{ algorithm outputs a number } < k/4 ] \leq \dfrac{1}{4} $$
3. Assuming that $U = [\mathsf{poly}(n)]$, what is the memory requirement of the algorithm above?

Problem 2 - Hardness of Approximation (25 points)

Given a graph $G$, an independent set is a set of vertices such that no two are neighbors. The Maximum Independent Set (MIS) problem is a famous NP-complete problem.

Interestingly, the complement of an independent set is a vertex cover, so the complement of the MIS is the minimum vertex cover. We’ve seen (twice) how to get a two-approximation for vertex cover. Even though it is complementary, the situation for MIS is much worse.

Early in the study of approximation hardness, MIS was shown to be MAX-SNP-hard, meaning there is some constant to within which it cannot be approximated (unless P = NP).

Suppose one has an $\alpha$-approximation algorithm for MIS. Consider the following graph product operation for a graph $G$. Create a distinct copy $G_v$ of $G$ for each vertex $v$ of $G$. Then connect up the copies as follows: if $(u,v)$ is an edge of $G$, then connect every vertex in $G_u$ to every vertex in $G_v$.

1. Prove that if there is an independent set of size $k$ in $G$, then there is an independent set of size $k^2$ in the product graph.
2. Prove that given an independent set of size $s$ in the product graph, one can find an independent set of size $\sqrt{s}$ in $G$.
3. Conclude from the MAX-SNP-hardness of MIS that MIS has no constant-factor approximation (unless P = NP).

Problem 3 - Proving that $\omega_{det} = \omega_{mult}$ (25 points)

Given a matrix $A \in \mathbb{Q}^{N \times N}$ where $N = 2^k$, prove that one can compute $\det(A)$ in time $O(n^\omega)$, where $\omega$ is the matrix multiplication exponent. You can assume that any matrix that you need to invert in the process is invertible.

Optional question: how would you remove the assumption given above?

Problem 4 - Consensus with Crash Failures (25 points)

We will now analyze the consensus problem in the synchronous model with crash failures. In this model, there are $n$ processors, which can communicate with one another by sending messages, and which are synchronized (thus communication happens in rounds).

We will assume that there will be at most $f$ processors that will crash, where $f \leq n$. Once a processor crashes, it will not be able to send or receive messages anymore. While the processors are alive, they will not be malicious, and will follow the proposed protocol.

There are two types of crashes: clean and general.

• In a clean crash, if a processor crashes at round $t$, then it will not send or receive any messages at round $t$ or later.
• In a general crash, if a processor $p_j$ crashes at round $t$, then an arbitrary subset of the messages that $p_j$ sends at round $t$ will be delivered to the other processors.

The setup of the consensus problem is as follows:

• Input: Each processor $i$ has an input value $x_i \in \mathbb{N}$.
• Output: Each processor $i$ should output a value $y_i$ such that:
  • Agreement: All alive processors output the same value.
  • Validity: If all processors have the same input value $v$, then $y_i = v$ for any alive processor.
  • Termination: All alive processors must output a value at the end.

Part 1 (10 points): give a protocol for consensus in the synchronous model with clean crashes, using one round of communication.

Part 2 (15 points): when there are general crashes, the processors can no longer reach consensus in one round. Hence, we will need a more resilient protocol to reach consensus.

Consider the following protocol for consensus under general crashes, where $f$ is the number of crash failures:

Protocol: Consensus with at most $f$ crash failures

Code for Processor $p_i$

1. Initially, set $V = \{x_i\}$
2. For round $k = 1, 2, \ldots, f+1$ do:
   • Send $U := \{ v \in V \mid p_i \text{ has not yet sent } v \}$ to all processors
   • Receive $U_j$ from processor $p_j$
   • Set $V := V \cup \bigcup_{j\neq i} U_j$
   • if $k = f+1$, output $\min V$

To prove correctness of the protocol above, let $V_i^{(k)}$ be the set $V$ at the end of round $k$ for processor $p_i$. Prove the following lemma (from which correctness easily follows):

1. In every execution of the protocol, $V_i^{(f+1)} = V_j^{(f+1)}$ for any two alive processors $p_i$ and $p_j$.

Practice Problems

You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)

Problem 1

You are building a real-time analytics system for a popular blogging platform. The platform has millions of users around the world who are constantly reading different blog posts. Your task is to find the number of unique blog posts read by each user in the past day. Due to the large scale of the platform, you can’t store all the user activity data in memory at once. Also, due to the dynamic nature of the world the data comes to you in a data stream.

The data stream contains a sequence of tuples, where each tuple consists of a user ID and a blog post ID. For example, a tuple may look like this: (“UserID_123”, “BlogPostID_456”), which indicates that User 123 has read Blog Post 456.

Assume that during one day there are $N$ posts being read (so the stream has total size of $N$ tuples, and you know $N$ in advance), and that you are only allowed 1 pass through the data stream.

You need to develop and analyze an algorithm that does the following:

• Processes each tuple from the stream one by one.
• provides a list of users that have read more than $20\%$ of the total number of posts (that is, $20\%$ of $N$). Your list should include all such users (but may also contain more users)
• your algorithm should use $O(\log N)$ memory

Problem 2

Remember that the characteristic polynomial of a matrix $A$ is the univariate polynomial given by $$ p_A(t) = \det(tI - A). $$

Define the problem of computing the characteristic polynomial of a matrix $A$ as the problem of computing the coefficients of $p_A(t)$. Prove that $\omega_{\text{characteristic polynomial}} \leq \omega + 1$.

Hint: First note that if I can evaluate a univariate polynomial $p(t)$ of degree $d$ at $d+1$ distinct points, then I can compute all coefficients of $p(t)$ by inverting one matrix. Try to express the relation of evaluating a polynomial of degree $d$ at $d+1$ points as a matrix vector multiplication.

Clarification: in class we only saw how to compute the determinant and the inverse of a matrix of field elements. You should only need to use these facts.