Let \(v_1, \ldots , v_n \in \{ 0,1\} ^{(\log n)^{k}}\) be an instance of \((1 + \tfrac {1}{\log \log n})\text{-}\mathsf{MSD}_{n, (\log n)^{k}}\). Construct \(V' = \{ v_1^{\otimes q}, \ldots , v_n^{\otimes q}\} \) for \(q = \frac{\log n}{(\log \log n)^{2}}\). The vectors of \(V'\) have dimension \((\log n)^{kq} = (\log n)^{\frac{k\log n}{(\log \log n)^{2}}}\), so the assumed algorithm applies and finds a \(\gamma \)-approximation of MSD on \(V'\) for some \(\gamma \le (1 + \tfrac {1}{\log \log n})^{q}\). By Lemma 4,

for all \(i,j\). Therefore a \(\gamma \)-approximation of MSD on \(V'\) is a \(\gamma ^{1/q} = (1 + \tfrac {1}{\log \log n})\)-approximation of MSD on \(v_1, \ldots , v_n\). The running time is preserved up to the \(O(n^{2-\varepsilon })\) bound.

(\(\Leftarrow \)) Given a bichromatic \((\log n)\)-Additive-Max-IP\(_{n,\ell '}\) instance with sets \(A = \{ a_1, \ldots , a_n\} \), \(B = \{ b_1, \ldots , b_n\} \) and threshold \(\alpha \), construct \(A' = \{ a_1', \ldots , a_n'\} \), \(B' = \{ b_1', \ldots , b_n'\} \) as follows: for each \(a_i\) first attach \(\ell - \lVert a_i \rVert _1\) zeros at the end and then another \(\ell - \lVert a_i \rVert _1\) ones to obtain \(a_i' \in \{ 0,1\} ^{3\ell }\), and for each \(b_j\) attach \(\ell + \lVert b_j \rVert _1\) zeros and another \(\ell - \lVert b_j \rVert _1\) ones to obtain \(b_j' \in \{ 0,1\} ^{3\ell }\). Now every \(a_i'\) and \(b_j'\) has exactly \(\ell \) ones, so \(\lVert a_i' \rVert = \lVert b_j' \rVert = \sqrt{\ell }\), and \(\langle a_i', b_j' \rangle = \langle a_i, b_j \rangle \) by the construction (the appended coordinates never overlap on a \(1\)). Hence running an \(\frac{\log n}{\ell }\)-Additive-MSD algorithm on \(A', B'\) with threshold \(\frac{\alpha }{\ell }\) distinguishes:

• there exists \((a',b')\) with \(\frac{\langle a', b' \rangle }{\lVert a' \rVert \lVert b' \rVert } \ge \frac{\alpha }{\ell }\), equivalent to \(\langle a, b \rangle \ge \alpha \); or

• for all \((a',b')\), \(\frac{\langle a', b' \rangle }{\lVert a' \rVert \lVert b' \rVert } {\lt} \frac{\alpha }{\ell } - \frac{\log n}{\ell }\), equivalent to \(\langle a, b \rangle {\lt} \alpha - \log n\) for all \(a \in A\), \(b \in B\).

The running time is \(O(n^{2-\varepsilon }\operatorname {poly}(3\ell )) = O(n^{2-\varepsilon }\operatorname {poly}(\ell ))\).

(\(\Rightarrow \)) Conversely, given a bichromatic \(\frac{\log n}{\ell }\)-Additive-MSD\(_{n,\ell }\) instance with sets \(A, B\) and threshold \(\alpha \), build the exact same \(A', B'\) so that \(\langle a_i', b_j' \rangle = \langle a_i, b_j \rangle \) and \(\lVert a_i' \rVert = \lVert b_j' \rVert = \sqrt{\ell }\) for all \(i,j\). The same argument shows that running an Additive-Max-IP algorithm on \(A', B'\) with threshold \(\alpha \cdot \ell \) solves the Additive-MSD instance.

By Theorem 46, the assumed \((1+\tfrac {1}{\log \log n})\)-MSD algorithm yields a truly subquadratic algorithm for bichromatic \((\log n)\)-Additive-Max-IP. By Lemma 47, bichromatic \((\log n)\)-Additive- Max-IP is subquadratic equivalent to bichromatic \(\frac{\log n}{\ell }\)-Additive-MSD, so the latter is also truly subquadratic.