Since \(v\) and \(w\) are nonzero, \(\| v\| \| w\| {\gt}0\). Dividing by this positive denominator preserves whether the numerator is zero, so \(\left\langle v,w\right\rangle /(\| v\| \| w\| )=0\) exactly when \(\left\langle v,w\right\rangle =0\).

Suppose, toward contradiction, that an algorithm \(A\) solves \(\gamma \)-\(\mathrm{LSD}_{n,c\log n}\) in \(O(n^{2-\varepsilon })\) time for the constants needed by OVC. Given an OV instance, first check in \(O(n\ell )\) time whether any vector is zero; if so, answer yes. Otherwise all vectors are nonzero and the LSD objective is well-defined. Run \(A\) and inspect the returned pair. By Lemma 186, the optimum LSD value is \(0\) exactly when the OV instance has an orthogonal pair. Any multiplicative \(\gamma \)-approximation to an optimum of \(0\) must also return value \(0\), while if no orthogonal pair exists every cosine similarity is positive. Thus this decides \(\mathrm{OV}_{n,c\log n}\) in \(O(n\ell +n^{2-\varepsilon })=O(n^{2-\varepsilon '})\) time, contradicting OVC, and hence SETH through Theorem 106.

Exact LSD is at least as hard as approximate LSD because an exact optimum is a valid approximation. Bichromatic LSD is harder than monochromatic LSD by Lemma 185. If every threshold problem \(\mathrm{LSD}_{n,\ell ,t}\) were truly subquadratic, then Lemma 184 would give a truly subquadratic exact LSD algorithm, contradicting Theorem 187. Therefore at least one threshold \(t\) is hard.

Substitute Lemma 9 into the numerator and Lemma 10 into both denominator factors. The resulting ratio is \(\left\langle v,w\right\rangle ^q/(\| v\| ^q\| w\| ^q)\), which is the \(q\)th power of the original cosine similarity.

Given vectors in dimension \((\log n)^k\), set \(q=\log n/(\log \log n)^2\) and replace every vector \(v_i\) by \(v_i^{\otimes q}\). The new dimension is \((\log n)^{k\log n/(\log \log n)^2}\), which has the form required by the assumed algorithm. By Lemma 190, every cosine similarity is raised to the \(q\)th power. Therefore a \(\gamma \)-approximation after tensoring becomes a \(\gamma ^{1/q}\)-approximation before tensoring, and the stated bound on \(\gamma \) makes this at most \(1+1/\log \log n\).

The appended block of \(a'\) containing ones is paired with a zero block of \(b'\), and the appended block of \(b'\) containing ones is paired with a zero block of \(a'\). Hence all appended coordinates contribute zero to the cross inner product, while the first \(\ell \) coordinates contribute exactly \(\left\langle a,b\right\rangle \). The number of ones in \(a'\) is \(\| a\| _1+(\ell -\| a\| _1)=\ell \), and the same calculation gives \(\ell \) ones for \(b'\).

By Lemma 193, both padded vectors have exactly \(\ell \) binary one-coordinates, so their Euclidean norms are \(\sqrt{\ell }\). The same lemma gives \(\left\langle a',b'\right\rangle =\left\langle a,b\right\rangle \), and substituting these identities into the cosine-similarity formula gives \(\left\langle a,b\right\rangle /(\sqrt{\ell }\sqrt{\ell })=\left\langle a,b\right\rangle /\ell \). Scaling both the threshold and the additive gap by this common factor preserves the promised yes/no separation.

Given a bichromatic additive Max-IP instance \(A,B\subseteq \{ 0,1\} ^{\ell }\) with threshold \(\alpha \), replace each \(a\in A\) by \(a'=(a,1^{\ell -\| a\| _1},0^{\ell +\| a\| _1})\) and each \(b\in B\) by \(b'=(b,0^{\ell +\| b\| _1},1^{\ell -\| b\| _1})\). Then every new vector has exactly \(\ell \) ones, and Lemma 194 says that the cosine similarity of \(a',b'\) is \(\left\langle a,b\right\rangle /\ell \). Thus the additive Max-IP threshold \(\alpha \) becomes the additive MSD threshold \(\alpha /\ell \), with the additive gap scaled by \(1/\ell \).

Conversely, given an additive MSD instance, apply the same padding so all new vectors have equal norm \(\sqrt{\ell }\) while preserving cross inner products. A cosine threshold \(\alpha \) becomes the Max-IP threshold \(\alpha \ell \), and an additive cosine gap of \((\log n)/\ell \) becomes an additive inner-product gap of \(\log n\). The dimension only triples.

Lemma 191 converts the assumed high-dimensional approximate MSD algorithm into a truly subquadratic \((1+1/\log \log n)\)-approximate MSD algorithm in every polylogarithmic dimension. Theorem 192 then yields a truly subquadratic additive Max-IP algorithm. Lemma 195 transfers between the additive MSD and additive Max-IP formulations with only logarithmic dimension blowup. Finally Theorem 196 converts this into a truly subquadratic OV algorithm, contradicting OVC.

If such an MSD algorithm existed for all constants required by OVC, then Lemma 197 would imply a truly subquadratic algorithm for \(\mathrm{OV}_{n,c'\log n}\) for every constant \(c'{\gt}0\). This contradicts OVC, and contradicts SETH through Theorem 106.

Exact MSD is at least as hard as approximate MSD. Bichromatic variants are harder by Lemma 185. If every decision threshold were truly subquadratic, Lemma 179 would make exact MSD truly subquadratic, contradicting Theorem 198.

The exact statement is the combination of Theorem 187 for approximate LSD and Corollary 188 for exact, threshold, and bichromatic variants.

This is precisely Theorem 198 together with Corollary 199.

The bichromatic setting avoids the monochromatic tensor-power loss. The paper routes logarithmic-dimensional bichromatic MSD through the corresponding bichromatic Max-IP hardness: equal-norm padding preserves cross inner products as cosine similarities, and the cited additive/Max-IP hardness supplies the OV contradiction in logarithmic dimension.