- 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.

- Write detailed pseudo-code for the reduction from MinPlusMatrixProduct to AllPairsNegTriangle, correctly handling the case where matrix entries are \(\infty\).
- 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).

- 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})\).