Algorithm to maximize dot product between two sets of vectors
As a completely different approach, assuming that $d &lt; \log n$, one can generate $O(\log n)$ random vectors $w_i$ with unit norm. For each $w_i$ we look at $\langle l_i, w_i \rangle$ and $\langle r_i, w_i \rangle$. Take the top largest $O(\sqrt n)$ from each list, as potential candidates. After completing we have $O(\sqrt n \log n)$ candidates, and then we check the dot products between the pairs. It is important that $d &lt; \log n$ so that $O(\log n)$ vectors are sufficient to cover the unit sphere well. In your case where $d = 4$ it would seem to be that $d &lt;&lt; \log n$.