# Homework 4

1. The problem TransitiveClosure is defined as follows: Given a directed graph $$G$$ on $$n$$ vertices, compute for each pair $$u, v$$ of vertices if there is a directed path from $$u$$ to $$v$$.

In other words, the output size is $$n^{2}$$ bits, and the problem can be solved by computing APSP.

Is the problem "as hard" as APSP?

Either give a subcubic algorithm for TransitiveClosure, or give a subcubic reduction from APSP or from an equivalent problem to TransitiveClosure.

2. Write detailed pseudo-code for the reduction from MinPlusMatrixProduct to AllPairsNegTriangle, correctly handling the case where matrix entries are $$\infty$$.
3. Consider the following hypothesis:

UnbalancedOrthogonalVectorsHypothesis: Given two sets $$A, B \subseteq \{0, 1\}^d$$ such that $$|A| = n$$, $$|B| = \sqrt{n}$$. There is no algorithm running in time $$O(n^{1.5−\varepsilon} \cdot poly(d))$$ (for any $$\varepsilon > 0$$) which decides whether there exist $$a \in A$$, $$b \in B$$ such that $$a$$ and $$b$$ are orthogonal.

Prove that UnbalancedOrthogonalVectorsHypothesis is equivalent to the orthogonal vectors hypothesis (OVH).

4. Consider the problem LongestPalindromeSubsequence:

Given a sequence $$S$$ of length $$n$$, find the longest subsequence which is a palindrome (that is, a sequence of characters which reads the same backward or forward).

Prove that SETH implies that there is no algorithm for LongestPalindromeSubsequence of runnning time $$O(n^{2−\varepsilon})$$.

Deadline: June 9, beginning of class.