\section{Proofs for Sections~\ref{sec:prelim} and~\ref{sec:threshold}}\label{app:threshold}

\lemperturb*

\begin{proof}
\begin{steps}
\step{1}{1} For every $j$, $e^{-2\eta}\pi_{ij}\le\pi'_{ij}\le e^{2\eta}\pi_{ij}$.
\pf The numerator $e^{\ell'_{ij}}$ lies in $[e^{-\eta}e^{\ell_{ij}},e^{\eta}e^{\ell_{ij}}]$, and so does the
denominator $\sum_{j'}e^{\ell'_{ij'}}$ relative to $\sum_{j'}e^{\ell_{ij'}}$.
\step{1}{2} $\sum_j|\pi'_{ij}-\pi_{ij}|\le e^{2\eta}-1$.
\pf By \sref{1}{1}, $|\pi'_{ij}-\pi_{ij}|\le\max\{e^{2\eta}-1,1-e^{-2\eta}\}\pi_{ij}=(e^{2\eta}-1)\pi_{ij}$, and
$\sum_j\pi_{ij}=1$.
\qedstep{1}{3}
\pf For every value coordinate $c$, $|o'_{ic}-o_{ic}|=|\sum_j(\pi'_{ij}-\pi_{ij})v_{jc}|\le\sum_j|\pi'_{ij}-\pi_{ij}|$,
because $|v_{jc}|\le1$. Apply \sref{1}{2}.
\end{steps}
\end{proof}

\subsection{Sampling}\label{app:sampling}

\thmsampling*

\begin{proof}
\begin{steps}
\step{1}{1} \Let $\eta=\eps/4$. Fix a query $i$, \Let $M=\max_j\ell_{ij}$, $w_j=e^{\ell_{ij}-M}\in(0,1]$,
$\mu=\frac1{n'}\sum_jw_j$ and $\nu_c=\frac1{n'}\sum_jw_jv_{jc}$ for each value coordinate $c$. Then
$o_{ic}=\nu_c/\mu$, $|\nu_c|\le\mu$ and $\mu\ge1/F$.
\pf $\pi_{ij}=w_j/(n'\mu)$, so $o_{ic}=\nu_c/\mu$, and $|\nu_c|\le\mu$ because $|v_{jc}|\le1$. Some $w_j$
equals $1$, so $F\ge n'\max_j\pi_{ij}=1/\mu$.
\step{1}{2} \Let the algorithm draw, for each query $i$ independently, indices $j_1,\dots,j_m$ uniformly
from $[n']$ with replacement, and output $\tilde o_{ic}=\sum_se^{\ell_{ij_s}}v_{j_sc}/\sum_se^{\ell_{ij_s}}$. It
uses $O(nm(d+d_v))$ operations, and in exact arithmetic $\tilde o_{ic}=\hat\nu_c/\hat\mu$ with
$\hat\mu=\frac1m\sum_sw_{j_s}$ and $\hat\nu_c=\frac1m\sum_sw_{j_s}v_{j_sc}$.
\pf Each query computes $m$ logits in $O(md)$ operations and two weighted sums in $O(md_v)$ operations.
Multiplying numerator and denominator by $e^{-M}$ does not change the ratio.
\step{1}{3} For fixed $i$ and $c$, each of the events $|\hat\mu-\mu|>\eta\mu$ and $|\hat\nu_c-\nu_c|>\eta\mu$
has probability at most $\delta/(n(1+d_v))$.
\begin{steps}
\step{2}{1} The summands $X_s=w_{j_s}$, respectively $X_s=w_{j_s}v_{j_sc}$, are independent, satisfy
$|X_s|\le1$, have mean $\mu$, respectively $\nu_c$, and variance at most $\mu$.
\pf $|X_s|\le w_{j_s}\le1$, so $X_s^2\le w_{j_s}^2\le w_{j_s}$ and $\mathrm{Var}(X_s)\le\mathbb E[w_{j_s}]=\mu$.
\step{2}{2} By Bernstein's inequality for independent variables with $|X_s-\mathbb EX_s|\le2$,
the probability that the empirical mean deviates by more than $t=\eta\mu$ is at most
$2\exp\bigl(-mt^2/(2\mu+4t/3)\bigr)\le2\exp(-3m\eta^2\mu/7)$.
\pf $mt^2/(2\mu+4t/3)=m\eta^2\mu/(2+4\eta/3)$ and $2+4\eta/3\le7/3$ because $\eta\le1/4$.
\qedstep{2}{3}
\pf By \sref{1}{1}, $\mu\ge1/F$, so the bound of \sref{2}{2} is at most $2\exp(-3m\eps^2/(112F))$, and
$m\ge40F\ln(2n(1+d_v)/\delta)/\eps^2$ makes it at most $\delta/(n(1+d_v))$, since $40>112/3$.
\end{steps}
\step{1}{4} With probability at least $1-\delta$, $|\hat\mu-\mu|\le\eta\mu$ and $|\hat\nu_c-\nu_c|\le\eta\mu$ for
all $i$ and $c$.
\pf A union bound over the $n(1+d_v)$ events of \sref{1}{3}.
\step{1}{5} On the event of \sref{1}{4}, $|\hat\nu_c/\hat\mu-\nu_c/\mu|\le2\eps/3$.
\pf $|\hat\nu_c/\hat\mu-\nu_c/\mu|\le|\hat\nu_c-\nu_c|/\hat\mu+(|\nu_c|/\mu)\,|\mu-\hat\mu|/\hat\mu\le
2\eta\mu/((1-\eta)\mu)$, using $|\nu_c|\le\mu$ and $\hat\mu\ge(1-\eta)\mu$. With $\eta=\eps/4\le1/4$ this is at
most $(\eps/2)(4/3)=2\eps/3$.
\step{1}{6} Evaluating the exponentials to relative precision $\eps/100$ changes $\tilde o_{ic}$ by at most
$\eps/3$.
\pf Compute the $m$ sampled logits to absolute error $\eps/1000$ and subtract their maximum before
exponentiating; then every weight lies in $(0,1]$, and every weight is computed to relative error at most
$e^{\eps/1000}(1+\eps/100)-1\le\eps/90$. The computed ratio is a weighted average of the same values with every
weight multiplied by a factor in $[1-\eps/90,1+\eps/90]$; as in \cref{lem:perturb}, this moves the average by
at most $(1+\eps/90)/(1-\eps/90)-1\le\eps/40$. If $m\ge n'$, the algorithm computes every output exactly instead,
with $O(nn'(d+d_v))\le O(nm(d+d_v))$ operations; so assume $m<n'$. The remaining $m$-term sums and the division are
carried out to relative precision $\eps/(1000m)$ per operation, on numbers of $O(\log(nm/\eps))=O(\log(nn'/\eps))$
bits. Every partial sum of the numerator is at most $\sum_sw_s$ in absolute value, because $|v_{j_sc}|\le1$, so the
numerator and the denominator are each computed within $(\eps/1000)\sum_sw_s$, and the ratio within
$3\eps/1000+\eps/(1000m)\le\eps/100$.
\step{1}{7} An instance with spread at most $\Spread$ satisfies $n'\pi_{ij}\le e^{\Spread}$.
\pf Every $w_j\ge e^{-\Spread}$, so $\mu\ge e^{-\Spread}$ and $n'\pi_{ij}=w_j/\mu\le e^{\Spread}$.
\qedstep{1}{8}
\pf By \sref{1}{4}, \sref{1}{5} and \sref{1}{6}, with probability at least $1-\delta$ every output is within
$2\eps/3+\eps/3=\eps$; \sref{1}{2} counts the operations and \sref{1}{7} gives the last sentence.
\end{steps}
\end{proof}

\subsection{Quadratic time above the threshold}\label{app:ldov-lb}

\thmldovlb*

\begin{proof}
\begin{steps}
\step{1}{1} \Let $c\ge1$ be the integer of \cref{hyp:ldov} for $\gamma/2$, \Let $\tau=\lceil4/\theta\rceil$, and
apply \cref{fact:chen} with parameters $c$, $\gamma/4$ and $\tau$; it gives $n_0$, a dimension
$d_{\mathrm C}\le\tau^{\poly(4c/\gamma)}\log n$ and an integer $T\ge c\log n$. \Let $C=2\tau^{\poly(4c/\gamma)}$,
so that $d_{\mathrm C}+1\le\lceil C\log n\rceil$, and \Let $\eta=(1-2\eps)/4$.
\pf $1\le\tau^{\poly(4c/\gamma)}\log n$ for $n\ge2$. Also $\eta\in(0,1/4]$.
\step{1}{2} \Assume an algorithm $\mathcal A$ solves $\ATT(n,\lceil C\log n\rceil,(1+\theta)\ln n,\eps)$ in
time $O(n^{2-\gamma})$ on the instances described in the theorem. \Prove $\OV_{n,\lceil c\log n\rceil}$ can
be solved in time $O(n^{2-\gamma/2})$, which contradicts the choice of $c$.
\step{1}{3} \Let $(A_\psi,B_\psi)$ be one of the instances of \cref{fact:chen}, \Let $\xi$ be a rational with
$\ln((1-\eta)/\eta)\le\xi\le\ln((1-\eta)/\eta)+1/10$, \Let $\lambda$ be a rational of $O(\log n)$ bits with
$\ln n+2\ln(1/\eta)+1/10\le\lambda T(1-1/\tau)\le\ln n+2\ln(1/\eta)+1/5$, computed from rational approximations of
$\ln n$ and $\ln(1/\eta)$, and \Let $t^*=\lambda T-\xi$. \Let the attention instance $I_\psi$ have the queries $q_x=(\lambda x,t^*)$ for
$x\in A_\psi$ and one zero query, the keys $k_y=(y,0)$ with value $1$ for $y\in B_\psi$, and the dummy key
$k^*=(0,1)$ with value $0$.
\pf $I_\psi$ has $n+1$ queries, $n+1$ keys, dimension $d_{\mathrm C}+1$, $d_v=1$, values in $\{0,1\}$ and
rational entries of $O(\log n)$ bits.
\step{1}{4} Every logit of $I_\psi$ lies in $[0,\lambda T]$, and $\lambda T\le(1+\theta)\ln(n+1)$ for all
$n\ge n_1(\theta,\eps)$.
\begin{steps}
\step{2}{1} $\ln n+2\ln(1/\eta)+1/10\le\lambda T(1-1/\tau)$ and $\lambda T\le(\ln n+2\ln(1/\eta)+1/5)/(1-1/\tau)$.
\pf By the choice of $\lambda$.
\step{2}{2} The logits of $q_x$ are $\lambda\ip xy\in[0,\lambda T]$ and $t^*\in[0,\lambda T]$; the zero query has
all logits $0$.
\pf \cref{fact:chen}(i) gives $\ip xy\in[0,T]$. By \sref{2}{1},
$\lambda T\ge\ln(1/\eta)+1/10\ge\xi$, since $\xi\le\ln((1-\eta)/\eta)+1/10$; so $t^*\ge0$.
\step{2}{3} $\lambda T\le(1+\theta/2)(\ln n+2\ln(1/\eta)+1/5)$.
\pf By \sref{2}{1} and $1/(1-1/\tau)\le1+2/\tau\le1+\theta/2$, because $1/\tau\le\theta/4\le1/4$.
\qedstep{2}{4}
\pf By \sref{2}{2} and \sref{2}{3}, since $(1+\theta/2)(2\ln(1/\eta)+1/5)\le(\theta/2)\ln n$ for
$n\ge n_1(\theta,\eps)$.
\end{steps}
\step{1}{5} \Let $o_x$ be the output of $q_x$ in $I_\psi$. If some $y\in B_\psi$ has $\ip xy=T$, then
$o_x\ge1-\eta$. If every $y\in B_\psi$ has $\ip xy\le T/\tau$, then $o_x\le\eta$.
\begin{steps}
\step{2}{1} $o_x=S_x/(S_x+e^{t^*})$ with $S_x=\sum_{y\in B_\psi}e^{\lambda\ip xy}$.
\pf The real keys have value $1$ and the dummy key has value $0$.
\step{2}{2} If $\ip xy=T$ for some $y$, then $o_x\ge1-\eta$.
\pf $S_x\ge e^{\lambda T}=e^{\xi}e^{t^*}$, so $o_x\ge e^{\xi}/(e^{\xi}+1)\ge1-\eta$, as $e^{\xi}\ge(1-\eta)/\eta$.
\step{2}{3} If $\ip xy\le T/\tau$ for all $y$, then $o_x\le\eta$.
\pf $o_x\le S_x/e^{t^*}\le n\exp(\lambda T/\tau-\lambda T+\xi)=ne^{\xi}e^{-\lambda T(1-1/\tau)}$. By \sref{1}{4},
this is at most $e^{\xi-1/10}\eta^2\le((1-\eta)/\eta)\eta^2\le\eta$.
\qedstep{2}{4}
\pf By \sref{2}{1}, \sref{2}{2} and \sref{2}{3}.
\end{steps}
\step{1}{6} \Let $N_\psi\le2n^{\gamma/4}$ be the number of instances. \Let the algorithm for $\OV$ solve inputs with
$n<\max\{n_0,n_1,\tau\}$ by brute force; otherwise it computes the instances of \cref{fact:chen}, builds each
$I_\psi$, runs $\mathcal A$ on it $R=\lceil18\ln(3N_\psi)\rceil$ times, and declares $\psi$ positive if in a
majority of the runs some query $q_x$ receives an output above $1/2$. It answers YES if and only if some
$\psi$ is positive. It errs with probability at most $1/3$.
\begin{steps}
\step{2}{1} A run of $\mathcal A$ that succeeds reports an output above $1/2$ for every query with
$o_x\ge1-\eta$, and for no query with $o_x\le\eta$. The zero query is ignored.
\pf A successful run is within $\eps$ of every output, and $1-\eta-\eps>1/2>\eta+\eps$, because
$\eta+\eps=(1+2\eps)/4<1/2$.
\step{2}{2} If $(A,B)$ has an orthogonal pair, some instance $\psi^*$ has a query with $o_x\ge1-\eta$. Otherwise
every query of every $I_\psi$ has $o_x\le\eta$.
\pf \cref{fact:chen}(ii) and (iii) with \sref{1}{5}.
\step{2}{3} If $(A,B)$ has an orthogonal pair, $\psi^*$ is declared positive with probability at least $1-1/(3N_\psi)$.
If not, each $\psi$ is declared positive with probability at most $1/(3N_\psi)$.
\pf Each run succeeds independently with probability at least $2/3$. By Hoeffding's inequality, at least
half of the $R$ runs fail with probability at most $e^{-R/18}\le1/(3N_\psi)$. If a majority succeeds, the
declaration about $\psi^*$, respectively about $\psi$, is the one given by \sref{2}{1} and \sref{2}{2}.
\qedstep{2}{4}
\pf On YES inputs, by \sref{2}{3} for $\psi^*$. On NO inputs, by \sref{2}{3} and a union bound over the
$N_\psi$ instances.
\end{steps}
\step{1}{7} The algorithm of \sref{1}{6} runs in time $O(n^{2-\gamma/2})$.
\pf \cref{fact:chen} takes time $n^{1+\gamma/4}\poly(\log n)$, building the instances takes
$N_\psi O(nd_{\mathrm C})$, and the calls take $N_\psi R\cdot O((n+1)^{2-\gamma})=O(n^{2-3\gamma/4}\log n)$.
By \sref{1}{1} and \sref{1}{4}, each $I_\psi$ is an instance of
$\ATT(n+1,\lceil C\log(n+1)\rceil,(1+\theta)\ln(n+1),\eps)$ of the stated form, so the assumption on $\mathcal A$
applies.
\qedstep{1}{8}
\pf \sref{1}{6} and \sref{1}{7} contradict \cref{hyp:ldov} for $\gamma/2$, so the algorithm $\mathcal A$ of
\sref{1}{2} does not exist.
\end{steps}
\end{proof}

\begin{remark}\label[remark]{rem:entries}
The instances $I_\psi$ in the proof of \cref{thm:ldovlb} can be written in the normalization $\exp(QK^\top/d')$ of~\cite{AS23} with all
entries in $[-B,B]$ for $B^2=O_{\gamma,\theta,\eps}(\ln n)$ and $d'=O_{\gamma,\theta}(\log n)$.
\end{remark}

\begin{proof}
\begin{steps}
\step{1}{1} Replace the last coordinate by a block of $T+1$ coordinates. The query $q_x$ gets
$\lambda u$ there, where $u\in[0,1]^{T+1}$ has coordinate sum $t^*/\lambda\le T$; the dummy key gets the
all-ones vector; the real keys get zeros. All logits are unchanged.
\pf $\ip{\lambda u}{\ind}=t^*$, and the real keys contribute nothing in the new block.
\step{1}{2} Now every query entry lies in $[0,\lambda]$ and every key entry in $\{0,1\}$. \Let
$d'=d_{\mathrm C}+T+1$, \Let $s$ be a rational with $\sqrt{d'/\lambda}\le s\le2\sqrt{d'/\lambda}$, and \Let
$Q'=sQ$ and $K'=(d'/s)K$. Then $Q'K'^\top/d'=QK^\top$, and all entries of $Q'$ and $K'$ lie in $[-B,B]$ for
$B^2=4d'\lambda$.
\pf The entries of $Q'$ are at most $s\lambda\le2\sqrt{d'\lambda}$, and those of $K'$ at most
$d'/s\le\sqrt{d'\lambda}$.
\qedstep{1}{3}
\pf $d'\lambda\le(d_{\mathrm C}+T+1)(\ln n+2\ln(1/\eta)+1/5)/(T(1-1/\tau))$ by step \sref{2}{1} of \sref{1}{4} in the proof of \cref{thm:ldovlb}, and
$(d_{\mathrm C}+T+1)/T\le\tau^{\poly(4c/\gamma)}/c+2$ depends only on $\gamma$ and $\theta$, because $T\ge c\log n$. Finally
$d'\le2d_{\mathrm C}+1=O_{\gamma,\theta}(\log n)$, because $T\le d_{\mathrm C}$.
\end{steps}
\end{proof}

\corladditive*

\begin{proof}
\begin{steps}
\step{1}{1} Repeat the proof of \cref{thm:ldovlb} with $\tau=\lceil\log n\rceil$ in \sref{1}{1}, for
$n\ge16$. Then $d_{\mathrm C}\le\tau^{\poly(4c/\gamma)}\log n\le(\log n)^{C-1}$ for a constant $C$ and large $n$.
\pf \Cref{fact:chen} holds for every real $\tau\ge4$ once $n\ge n_0$, where $n_0$ does not depend on $\tau$, and
its dimension bound is explicit in $\tau$.
\step{1}{2} All logits lie in $[0,\lambda T]$ with $\lambda T\le\ln n+2\ln(1/\eta)+2$ for large $n$.
\pf By step \sref{2}{1} of \sref{1}{4} in that proof, $\lambda T\le(\ln n+2\ln(1/\eta)+1/5)(1+2/\log n)$, which is
$\ln n+2\ln(1/\eta)+1/5+2\ln2+o(1)$. Finally $2\ln(1/\eta)=2\ln(4/(1-2\eps))$, and for $\eps=1/6$ the bound is
$\ln n+2\ln6+2<\ln n+6$.
\qedstep{1}{3}
\pf Steps \sref{1}{5} and \sref{1}{6} of that proof use only items (i)--(iii) of \cref{fact:chen} and the bound
$\lambda T(1-1/\tau)\ge\ln n+2\ln(1/\eta)+1/10$, so they hold unchanged; the condition $1/\tau\le\theta/4$ was used
only for the spread bound, which \sref{1}{2} replaces. In step \sref{1}{7}, \cref{fact:chen} now takes time
$n^{1+\gamma/4}\poly(\log n)$ because $d_{\mathrm C}$ is polylogarithmic, building the instances takes
$N_\psi O(nd_{\mathrm C})=O(n^{1+\gamma/4}\poly(\log n))$, and the calls take $O(n^{2-3\gamma/4}\log n)$ as before; by
\sref{1}{1} and \sref{1}{2}, each $I_\psi$ is an instance of
$\ATT(n+1,\lceil(\log(n+1))^C\rceil,\ln(n+1)+2\ln(1/\eta)+2,\eps)$ of the stated form. Step \sref{1}{8} applies verbatim.
\end{steps}
\end{proof}

\subsection{The exponent below the threshold}\label{app:curve}

\thmcurve*

\begin{proof}
We may assume that $\alpha$ is rational. For real $\alpha$, choose a rational $\tilde\alpha\in(\alpha-\gamma,\alpha]$ and let
$\tilde\gamma=\gamma-\alpha+\tilde\alpha$, so that $0<\tilde\gamma<\tilde\alpha$; the rational case gives $C$ such that spread
$(1+\theta)\tilde\alpha\ln n\le(1+\theta)\alpha\ln n$ has no $O(n^{1+\tilde\alpha-\tilde\gamma})=O(n^{1+\alpha-\gamma})$ algorithm in
dimension $\lceil C\log n\rceil$, which is the claim for $\alpha$.
\begin{steps}
\step{1}{1} \Let $c$, $\tau=\lceil4/\theta\rceil$, $n_0$, $d_{\mathrm C}$, $T$, $C$ and $\eta$ be as in step \sref{1}{1} of the
proof of \cref{thm:ldovlb}, so that $c$ is the integer of \cref{hyp:ldov} for $\gamma/2$, \cref{fact:chen} is applied
with parameters $c$, $\gamma/4$ and $\tau$, and $d_{\mathrm C}+1\le\lceil C\log n\rceil$. \Let $x(\psi,\cdot)$ and $y$ be the maps
of \cref{fact:chen}(iv).
\pf As there.
\step{1}{2} \Assume an algorithm $\mathcal A$ solves $\ATT(N,\lceil C\log N\rceil,(1+\theta)\alpha\ln N,\eps)$ in time
$O(N^{1+\alpha-\gamma})$ on the instances described in the theorem. \Prove $\OV_{n,\lceil c\log n\rceil}$ can be solved
in time $O(n^{2-\gamma/2})$, which contradicts the choice of $c$.
\step{1}{3} \Let $(A,B)$ be an instance of $\OV_{n,\lceil c\log n\rceil}$ and $n_B=\lceil n^{\alpha}\rceil$. Partition $B$ into
$J$ groups $B_1,\dots,B_J$ of at most $n_B$ vectors each, and for each $j$ \Let $M_j=\lceil n/(|B_j|+1)\rceil$ and
$N_j=M_j(|B_j|+1)$. Then $J\le2n^{1-\alpha}$ and $n\le N_j\le2n$.
\pf $J=\lceil n/n_B\rceil\le n^{1-\alpha}+1$. $N_j\ge n$ by the choice of $M_j$, and $N_j<n+|B_j|+1$, so the integer
$N_j$ is at most $n+|B_j|\le2n$.
\step{1}{4} \Let $\xi$ be a rational with $\ln((1-\eta)/\eta)\le\xi\le\ln((1-\eta)/\eta)+1/10$, \Let $\lambda$ be a rational of
$O(\log n)$ bits with $\alpha\ln n+2\ln(1/\eta)+1\le\lambda T(1-1/\tau)\le\alpha\ln n+2\ln(1/\eta)+11/10$, computed from
rational approximations of $\ln n$ and $\ln(1/\eta)$, and \Let $t^*=\lambda T-\xi$. For each $j$ and $\psi$ \Let the instance
$I_{j,\psi}$ have the queries $q_a=(\lambda x(\psi,a),t^*)$ for $a\in A$ and $N_j-n$ zero queries; $M_j$ keys equal to
$(y(b),0)$ with value $1$ for each $b\in B_j$; and $M_j$ keys equal to $(0,1)$ with value $0$.
\pf $I_{j,\psi}$ has $N_j$ queries, $N_j$ keys, dimension $d_{\mathrm C}+1$, $d_v=1$, values in $\{0,1\}$ and rational
entries of $O(\log n)$ bits, and it is built in time $O(N_jd_{\mathrm C})$ from the vectors $x(\psi,a)$ and $y(b)$.
\step{1}{5} Every logit of $I_{j,\psi}$ lies in $[0,\lambda T]$, and $\lambda T\le(1+\theta)\alpha\ln n\le(1+\theta)\alpha\ln N_j$
for all $n\ge n_1(\alpha,\theta,\eps)$.
\begin{steps}
\step{2}{1} $\alpha\ln n+2\ln(1/\eta)+1\le\lambda T(1-1/\tau)\le\alpha\ln n+2\ln(1/\eta)+11/10$.
\pf By the choice of $\lambda$.
\step{2}{2} The logits of $q_a$ are $\lambda\ip{x(\psi,a)}{y(b)}\in[0,\lambda T]$ and $t^*\in[0,\lambda T]$; zero queries
have all logits $0$.
\pf \Cref{fact:chen}(i) and (iv) give $\ip{x(\psi,a)}{y(b)}\in[0,T]$. By \sref{2}{1}, $\lambda T\ge\ln(1/\eta)+1\ge\xi$,
since $\xi\le\ln((1-\eta)/\eta)+1/10$; so $t^*\ge0$.
\step{2}{3} $\lambda T\le(1+\theta/2)(\alpha\ln n+2\ln(1/\eta)+11/10)$.
\pf By \sref{2}{1} and $1/(1-1/\tau)\le1+2/\tau\le1+\theta/2$, because $1/\tau\le\theta/4\le1/4$.
\qedstep{2}{4}
\pf By \sref{2}{2} and \sref{2}{3}, since $(1+\theta/2)(2\ln(1/\eta)+11/10)\le(\theta/2)\alpha\ln n$ for
$n\ge n_1(\alpha,\theta,\eps)$, and $N_j\ge n$.
\end{steps}
\step{1}{6} \Let $o_a$ be the output of $q_a$ in $I_{j,\psi}$. If some $b\in B_j$ has $\ip{x(\psi,a)}{y(b)}=T$, then
$o_a\ge1-\eta$. If every $b\in B_j$ has $\ip{x(\psi,a)}{y(b)}\le T/\tau$, then $o_a\le\eta$.
\begin{steps}
\step{2}{1} $o_a=S_a/(S_a+e^{t^*})$ with $S_a=\sum_{b\in B_j}e^{\lambda\ip{x(\psi,a)}{y(b)}}$.
\pf Every key occurs $M_j$ times, so every term of the numerator and of the denominator of the softmax is
multiplied by $M_j$. The real keys have value $1$ and the dummy keys value $0$.
\step{2}{2} If $\ip{x(\psi,a)}{y(b)}=T$ for some $b\in B_j$, then $o_a\ge1-\eta$.
\pf $S_a\ge e^{\lambda T}=e^{\xi}e^{t^*}$, so $o_a\ge e^{\xi}/(e^{\xi}+1)\ge1-\eta$, as $e^{\xi}\ge(1-\eta)/\eta$.
\step{2}{3} If $\ip{x(\psi,a)}{y(b)}\le T/\tau$ for all $b\in B_j$, then $o_a\le\eta$.
\pf $o_a\le S_a/e^{t^*}\le n_B\exp(\lambda T/\tau-\lambda T+\xi)=n_Be^{\xi}e^{-\lambda T(1-1/\tau)}$. By \sref{2}{1} of
\sref{1}{5} and $n_B\le2n^{\alpha}$, this is at most $2e^{\xi-1}\eta^2\le2e^{-9/10}((1-\eta)/\eta)\eta^2\le\eta$, since
$2e^{-9/10}<1$.
\qedstep{2}{4}
\pf By \sref{2}{1}, \sref{2}{2} and \sref{2}{3}.
\end{steps}
\step{1}{7} \Let $N_\psi\le2n^{\gamma/4}$ be the number of indices $\psi$. \Let the algorithm for $\OV$ solve inputs with
$n<\max\{n_0,n_1,\tau\}$ by brute force; otherwise it computes $x(\psi,a)$ and $y(b)$ for all $\psi$, $a\in A$ and $b\in B$,
builds every $I_{j,\psi}$, runs $\mathcal A$ on it $R=\lceil18\ln(3JN_\psi)\rceil$ times, and declares $(j,\psi)$ positive
if in a majority of the runs some query $q_a$ receives an output above $1/2$. It answers YES if and only if some
$(j,\psi)$ is positive. It errs with probability at most $1/3$.
\begin{steps}
\step{2}{1} A run of $\mathcal A$ that succeeds reports an output above $1/2$ for every query with $o_a\ge1-\eta$,
and for no query with $o_a\le\eta$. The zero queries are ignored.
\pf $1-\eta-\eps>1/2>\eta+\eps$, because $\eta+\eps=(1+2\eps)/4<1/2$.
\step{2}{2} If $\ip{a^*}{b^*}=0$ with $a^*\in A$ and $b^*\in B_{j^*}$, then some $I_{j^*,\psi^*}$ has $o_{a^*}\ge1-\eta$. If
$(A,B)$ has no orthogonal pair, every query of every $I_{j,\psi}$ has $o_a\le\eta$.
\pf \Cref{fact:chen}(iv) and \sref{1}{6}.
\step{2}{3} In the first case $(j^*,\psi^*)$ is declared positive with probability at least $1-1/(3JN_\psi)$. In the
second, each $(j,\psi)$ is declared positive with probability at most $1/(3JN_\psi)$.
\pf Each run succeeds independently with probability at least $2/3$. By Hoeffding's inequality, at least half of
the $R$ runs fail with probability at most $e^{-R/18}\le1/(3JN_\psi)$. If a majority succeeds, the declaration is
the one given by \sref{2}{1} and \sref{2}{2}.
\qedstep{2}{4}
\pf On YES inputs, by \sref{2}{3} for $(j^*,\psi^*)$. On NO inputs, by \sref{2}{3} and a union bound over the
$JN_\psi$ instances.
\end{steps}
\step{1}{8} The algorithm of \sref{1}{7} runs in time $O(n^{2-\gamma/2})$.
\pf \Cref{fact:chen} takes time $n^{1+\gamma/4}\poly(\log n)$. Building the instances takes
$JN_\psi\cdot O(nd_{\mathrm C})=O(n^{2-\alpha+\gamma/4}\log n)$, and the calls take
$JN_\psi R\cdot O((2n)^{1+\alpha-\gamma})=O(n^{2-3\gamma/4}\log n)$. Both are $O(n^{2-\gamma/2})$, the first because
$\gamma<\alpha$. By \sref{1}{1} and \sref{1}{5}, after padding with zero coordinates each $I_{j,\psi}$ is an instance of
$\ATT(N_j,\lceil C\log N_j\rceil,(1+\theta)\alpha\ln N_j,\eps)$ of the stated form, so the assumption on $\mathcal A$
applies.
\qedstep{1}{9}
\pf \sref{1}{7} and \sref{1}{8} contradict \cref{hyp:ldov} for $\gamma/2$, so the algorithm $\mathcal A$ of \sref{1}{2}
does not exist.
\end{steps}
\end{proof}