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.