Homework 5
This homework covers the material from lectures 18 to 22
Due date: August 2nd.
PDF version of Homework 5.
LaTeX template, in case you want to write it in LaTeX.
Required Exercises
Remember that you are only required to turn in 5 out of the 6 exercises below.
Problem 1 - SDP Relaxation (20 points)
Given a 3-uniform hypergraph $G(V, E)$ (that is, a hypergraph where each hyperedge has exactly 3 vertices), we say that a 2-coloring of $V$ is valid for a hyperedge $e = \{ a, b, c\} \in E$ if the hyperedge $e$ is not monochromatic upon this coloring.
The Max-2C3U problem is the following:
- Input: a 3-uniform hypergraph $G(V, E)$
- Output: a 2-coloring of the vertices of $G$ of maximum value, that is, a function $f : V \rightarrow \{ -1, 1 \}$ (the coloring) which maximizes the number of valid hyperedges.
- Write the optimization problem above as a quadratic program
- Formulate an SDP relaxation for the problem, and prove that it is in fact a relaxation
Problem 2 - Hardness of Approximation (20 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$.
- 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.
- 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$.
- Conclude from the MAX-SNP-hardness of MIS that MIS has no constant-factor approximation (unless P = NP).
Problem 3 - Interactive Proofs and Complexity Classes (20 points)
Prove the following relations directly from the definitions of PCP, IP, NP, co-RP and P:
- $NP \subseteq IP$
- co-$RP \subseteq IP$
- $P = PCP[0,0]$
- $NP = PCP[0, \textsf{poly}(n)]$
- co-$RP = PCP[\textsf{poly}(n), 0]$
Problem 4 - Competitive Analysis (20 points)
You have reached a river (modelled as a straight line) and must find a bridge to cross it. The bridge is at some integer coordinate upstream or downstream.
- Give a 9-competitive deterministic algorithm for optimizing the total distance travelled up and downstream before you find the bridge.
- Give a randomized 7-competitive algorithm for the problem
Problem 5 - Paging Algorithms (20 points)
A conservative algorithm is one that makes at most $k$ page faults on any consecutive subsequence of the input that contains at most $k$ pages. Here $k$ is the size of the cache.
- Prove that LRU and FIFO are conservative
- Prove that any conservative algorithm is k-competitive.
Problem 6 - Proving that $\omega_{det} = \omega_{mult}$ (20 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?
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
Prove that the paging problem with a cache having $k$ pages is a special case of the $k$-server problem.
Hint: think of your metric space $X$ being the $n$-dimensional simplex.