\section{Proofs for Section~\ref{sec:precision}}\label{app:precision}

\subsection{Counting modulo \texorpdfstring{$r+1$}{r+1}}\label{app:parity}

\thmparity*

\begin{proof}
\begin{steps}
\step{1}{1} \Let $c\ge1$ be the integer of \cref{hyp:ldov} for $\gamma/2$, and \Assume an algorithm $\mathcal A$
solves the problem in the statement in time $O(N^{2-\gamma})$ on instances of size $N$ of the stated form.
\Prove $\OV_{n,m}$ with $m=\lceil c\log n\rceil$ can be solved in time $O(n^{2-\gamma/2})$, which contradicts the
choice of $c$.
\step{1}{2} \Let $(A,B)$ be an instance of $\OV_{n,m}$. If $0^m\in A$, the answer is YES. Otherwise every
$a\in A$ has $\ip a{\ind}\ge1$, where $\ind$ is the all-ones vector.
\pf The zero vector is orthogonal to every vector of $B$.
\step{1}{3} \Let $N=2n$, and \Let $n_2$ be such that $r(N')\le N'$ and $w(N')\le\frac12\log N'$ for all $N'\ge n_2$;
inputs with $2n<n_2$ are solved by brute force in time $O(1)$, so assume $N\ge n_2$. \Let $r=r(N)$, $w=w(N)$,
$K_0=\lceil m/w\rceil$, and partition $[m]$ into consecutive blocks $B_1,\dots,B_{K_0}$ of size at most $w$. For
$a,b'\in\{0,1\}^m$ \Let $F(a,b')$ be the number of blocks $t$ with
$a_kb'_k=1$ for some $k\in B_t$. Then $F(a,b')=\ip{\phi(a)}{\psi(b')}$, where $\phi(a)$ and $\psi(b')$ are indexed
by the pairs $(t,S)$ with $\emptyset\ne S\subseteq B_t$ and
\[
\phi(a)_{t,S}=(-1)^{|S|+1}\prod_{k\in S}a_k,\qquad \psi(b')_{t,S}=\prod_{k\in S}b'_k .
\]
They have $d_0=\sum_t(2^{|B_t|}-1)\le K_0(2^w-1)$ coordinates, with entries in $\{-1,0,1\}$ and $\{0,1\}$.
\pf For each block, $1-\prod_{k\in B_t}(1-a_kb'_k)$ is $1$ if $a$ and $b'$ share a one in $B_t$ and $0$ otherwise,
and expanding the product gives $\sum_{\emptyset\ne S\subseteq B_t}(-1)^{|S|+1}\prod_{k\in S}a_kb'_k$. Sum over $t$.
\step{1}{4} \Let $z=1+1/r$, $\lambda=\ln z$, $\eps_0=r^{K_0}/(32n(r+1)^{2K_0})$, and \Let $\lambda'$ be a rational with
$\lambda-\eps_0/(12K_0)\le\lambda'\le\lambda$. For a sublist $B'$ of $B$ \Let the instance $I(B')$ have the queries
$q_a=\lambda'\phi(a)$ for $a\in A$ and $n$ zero queries; for each $b'\in B$ a key equal to $\psi(b')$ if $b'\in B'$
and to $\psi(\ind)$ otherwise, with value $0$; and $n$ keys equal to $0$ with value $1$. Then $\lambda'>0$.
\pf $\lambda'$ exists with $O(\log(K_0/\eps_0))=O(K_0\log(r+1)+\log n)=O(\log^2n)$ bits, because $K_0\le m$ and
$r\le N$; this is $O(\log(N/\eps))$, as the model allows. It is positive because $\lambda=\ln(1+1/r)\ge1/(r+1)$, while
$\eps_0/(12K_0)\le1/(384n(r+1))$ since $r^{K_0}\le(r+1)^{K_0}$. $I(B')$ has $N$ queries, $N$ keys, dimension $d_0$,
$d_v=1$ and values in $\{0,1\}$. Since $w\le\frac12\log N$, $2^w\le\sqrt{2n}$ and $d_0\le m\sqrt{2n}$, so $I(B')$ is
computed in time $O(n^{3/2}\poly(\log n))$.
\step{1}{5} $I(B')$ is an instance of the problem in the statement for size $N$.
\pf $K_0\le\lceil\lceil c\log N\rceil/w\rceil=K$, so $d_0\le K(2^w-1)$ and padding with zero coordinates reaches
dimension $d$. A query $q_a$ has logits $\lambda'F(a,\cdot)\in[0,\lambda'K_0]\subseteq[0,\Spread]$ for the keys
$\psi(\cdot)$ and $0$ for the zero keys; zero queries have all logits $0$. The precision is handled in
\sref{1}{7}.
\step{1}{6} \Let $o_a$ be the output of $q_a$ when $\lambda'$ is replaced by $\lambda$, \Let
$S_a=\sum_{b'\in B}z^{F(a,\tilde b')}$, where $\tilde b'$ is $b'$ if $b'\in B'$ and $\ind$ otherwise, and \Let
$N_a=|\{b'\in B':\ip a{b'}=0\}|$. Then $o_a=n/(n+S_a)$, the number $X_a=r^{K_0}S_a$ is an integer, and
$X_a\equiv r^{K_0}N_a\pmod{r+1}$.
\begin{steps}
\step{2}{1} $o_a=n/(n+S_a)$.
\pf The $n$ zero keys have logit $0$ and value $1$; the other keys have value $0$ and weight
$e^{\lambda F(a,\tilde b')}=z^{F(a,\tilde b')}$.
\step{2}{2} For $0\le s\le K_0$, $r^{K_0}z^s=(r+1)^sr^{K_0-s}$ is an integer, divisible by $r+1$ if $s\ge1$, and equal
to $r^{K_0}$ if $s=0$.
\pf $z^s=(r+1)^s/r^s$, and $F$ takes values in $\{0,\dots,K_0\}$.
\step{2}{3} $F(a,\tilde b')=0$ holds exactly for the $N_a$ kept vectors $b'\in B'$ with $\ip a{b'}=0$.
\pf $F(a,b')=0$ if and only if $a$ and $b'$ share no one, that is, $\ip a{b'}=0$. For a dropped $b'$,
$F(a,\ind)\ge1$ by \sref{1}{2}.
\qedstep{2}{4}
\pf Sum \sref{2}{2} over the keys and use \sref{2}{3}.
\end{steps}
\step{1}{7} \Assume $\|\tilde o-o'\|_\infty\le\eps$ for the true outputs $o'$ of $I(B')$, with $\eps$ as in the
statement at size $N$, and \Let $\hat o_a$ be the multiple of $\eps_0/8$ nearest to $\min\{1,\max\{\eps_0,\tilde o_a\}\}$.
Then $X_a=\lfloor r^{K_0}n(1/\hat o_a-1)+1/2\rfloor$ for every $a\in A$.
\begin{steps}
\step{2}{1} $\eps\le\eps_0/2$.
\pf $\eps=1/(64N(r+1)^{2K})$ and $\eps_0/2\ge1/(64n(r+1)^{2K_0})$, since $r^{K_0}\ge1$, $n\le N$ and $K_0\le K$.
\step{2}{2} $|o'_a-o_a|\le\eps_0/4$.
\pf The logits of $q_a$ change by at most $\eta=K_0(\lambda-\lambda')\le\eps_0/12$, and \cref{lem:perturb} gives
$e^{2\eta}-1\le3\eta$ because $\eta\le1/4$.
\step{2}{3} \Let $E=z^{K_0}$. Then $o_a\ge1/(2E)\ge2\eps_0$ and $|\hat o_a-o_a|\le\eps_0$.
\pf $S_a\le nE$ gives $o_a\ge1/(1+E)\ge1/(2E)$, and $1/(2E)=r^{K_0}/(2(r+1)^{K_0})\ge2\eps_0$. By \sref{2}{1} and
\sref{2}{2}, $|\tilde o_a-o_a|\le3\eps_0/4$. Since $o_a\in[\eps_0,1]$, replacing $\tilde o_a$ by
$\min\{1,\max\{\eps_0,\tilde o_a\}\}$ does not increase its distance to $o_a$, and rounding to a multiple of $\eps_0/8$
adds at most $\eps_0/16$.
\step{2}{4} $|n(1/\hat o_a-1)-S_a|\le1/(4r^{K_0})$.
\pf By \sref{2}{3}, $\hat o_a\ge o_a-\eps_0\ge o_a/2$, and $S_a=n/o_a-n$ by \sref{1}{6}. So
$|n/\hat o_a-n/o_a|=n|o_a-\hat o_a|/(o_a\hat o_a)\le2n\eps_0/o_a^2\le8n\eps_0E^2=8n\eps_0(r+1)^{2K_0}/r^{2K_0}=1/(4r^{K_0})$.
\qedstep{2}{5}
\pf Multiply \sref{2}{4} by $r^{K_0}$: the real number $r^{K_0}n(1/\hat o_a-1)$ is within $1/4$ of the integer $X_a$.
\end{steps}
\step{1}{8} \Let the algorithm run $L=4$ rounds. In each round it draws $B'$ by keeping every $b'\in B$
independently with probability $1/2$, runs $\mathcal A$ on $I(B')$ independently $R=\lceil18\ln40\rceil$ times,
takes the coordinatewise median $\tilde o$, computes $\hat o_a$ and $X_a$ as in \sref{1}{7} and
$\rho_a=X_a\cdot(r^{K_0})^{-1}\bmod(r+1)$ for every $a$. It answers YES if some $\rho_a\ne0$ in some round, and NO otherwise. It errs with probability at
most $1/3$.
\begin{steps}
\step{2}{1} In each round, with probability at least $39/40$, the median satisfies the hypothesis of
\sref{1}{7}, and then $\rho_a=N_a\bmod(r+1)$ for all $a$.
\pf Each run satisfies $\|\cdot-o'\|_\infty\le\eps$ with probability at least $2/3$. By Hoeffding's inequality, at
least half of the runs fail with probability at most $e^{-R/18}\le1/40$. Otherwise, in every coordinate more than
half of the values lie within $\eps$ of $o'$, and so does their median. Then \sref{1}{7} and \sref{1}{6} give
$X_a\equiv r^{K_0}N_a$, and $r^{K_0}$ is invertible modulo $r+1$ since $\gcd(r,r+1)=1$.
\step{2}{2} If $(A,B)$ has no orthogonal pair, the algorithm answers NO with probability at least $9/10$.
\pf All $N_a=0$; by \sref{2}{1}, with probability at least $1-4/40$ every $\rho_a$ in every round is $0$.
\step{2}{3} If $\ip{a^*}{b^*}=0$ for some $a^*\in A$ and $b^*\in B$, then in each round
$N_{a^*}\not\equiv0\pmod{r+1}$ with probability at least $1/2$, independently of the other rounds.
\pf Condition on the choices for all $b'\ne b^*$. The two possible values of $N_{a^*}$ differ by $1$, and at most
one of them is divisible by $r+1\ge2$.
\qedstep{2}{4}
\pf By \sref{2}{2}, the error on NO instances is at most $1/10$. On YES instances, by \sref{2}{3} no round has
$N_{a^*}\not\equiv0$ with probability at most $1/16$, and by \sref{2}{1} some median is inaccurate with
probability at most $1/10$; otherwise $\rho_{a^*}\ne0$ in some round. The error is at most $1/16+1/10<1/3$.
\end{steps}
\step{1}{9} The algorithm runs in time $O(n^{2-\gamma/2})$.
\pf Computing $r(N)$ and $w(N)$ takes time $O(n)$. Building the $L$ instances takes time
$O(n^{3/2}\poly(\log n))$ by \sref{1}{4}. The algorithm makes $LR=O(1)$ calls of $\mathcal A$ on instances of size
$N=2n$, each in time $O(n^{2-\gamma})$. Reading their outputs, taking the medians by comparisons, and truncating each
median to $O(\log(1/\eps_0))$ bits before rounding cost $O(R)$ times the length of the outputs, which is at most the
running time of the calls. Computing $\lambda'$ to $O(\log^2n)$ bits takes $\poly(\log n)$ time. Each $\hat o_a$ is a multiple
of $\eps_0/8$ in $[\eps_0,1+\eps_0]$, so the $X_a$ and $\rho_a$ take $n\poly(\log n)$ operations on numbers of
$O(K_0\log(r+1)+\log n)=O(\log^2n)$ bits. The total is $O(n^{2-\gamma}+n^{3/2}\poly(\log n))=O(n^{2-\gamma/2})$, because
$\gamma<1$.
\qedstep{1}{10}
\pf \sref{1}{8} and \sref{1}{9} contradict the choice of $c$ in \sref{1}{1}.
\end{steps}
\end{proof}

\subsection{The polynomial method}\label{app:polymethod}

\thmpoly*

\begin{proof}
\begin{steps}
\step{1}{1} \Let $A_0=C/\ln2+3$, choose $\gamma_0\in(0,1]$ with $\gamma_0\ln(eA_0/\gamma_0)\le\eta/2$, and \Let
$\kappa=\min\{1/4,(\gamma_0/(2e))\exp(-(\beta+4)/\gamma_0)\}$, $R=2\kappa\ln n$ and $g=\lceil\gamma_0\ln n\rceil$.
\pf $\gamma\ln(eA_0/\gamma)\to0$ as $\gamma\to0$, so $\gamma_0$ exists.
\step{1}{2} Appending the coordinate $-\ip{q_i}{k_1}$ to each $q_i$ and the coordinate $1$ to each key gives an
instance with the same outputs, dimension at most $C\log n+1$, and all logits in $[-\kappa\ln n,\kappa\ln n]$.
\pf The logits of row $i$ become $\ell_{ij}-\ell_{i1}$, a shift that does not change $\pi_{ij}$, and they lie in
$[-\kappa\ln n,\kappa\ln n]$ because the spread is at most $\kappa\ln n$.
\step{1}{3} \Let every entry of the shifted queries, of the keys and of the values be rounded to the nearest
multiple of $2^{-L}$, with $L=\lceil K_1\log n\rceil$ for a constant $K_1$ depending on $\beta$ and on the bit length of the
input. For large $n$ this changes every logit by at most $n^{-\beta-3}$, moves every output by at most $4n^{-\beta-3}$, and
afterwards every entry is an integer multiple of $2^{-L}$ of absolute value at most $n^{K_1}$.
\pf The input entries are rationals of $O(\log n)$ bits, hence at most $n^{K_2}$ in absolute value for a constant
$K_2$, and so are the shifted entries. A logit is a sum of at most $C\log n+1$ products, each of which changes
by at most $2n^{K_2}2^{-L}+2^{-2L}$; with $K_1\ge K_2+\beta+5$ the total is at most $n^{-\beta-3}$. \Cref{lem:perturb}
bounds the effect of the logits by $e^{2n^{-\beta-3}}-1\le3n^{-\beta-3}$, and rounding the values moves each output by at
most $2^{-L}\le n^{-\beta-3}$.
\step{1}{4} \Let $P_g(x)=\sum_{t<g}x^t/t!$. For $|x|\le R$, $|P_g(x)/e^x-1|\le e^{2R}(eR/g)^g\le n^{-\beta-2}$ for large $n$.
\pf By Taylor's theorem with Lagrange remainder, $|e^x-P_g(x)|\le e^RR^g/g!$; divide by $e^x\ge e^{-R}$ and use
$g!\ge(g/e)^g$. Then $eR/g\le2e\kappa/\gamma_0\le\exp(-(\beta+4)/\gamma_0)$, so $(eR/g)^g\le n^{-\beta-4}$, and $e^{2R}=n^{4\kappa}\le n$.
All rounded logits lie in $[-R,R]$, because $\kappa\ln n+n^{-\beta-3}\le R$.
\step{1}{5} \Let $\Phi_q(x)=(x^\alpha/\alpha!)_{|\alpha|<g}$ and $\Phi_k(x)=(x^\alpha)_{|\alpha|<g}$, indexed by multi-indices
$\alpha$ with $|\alpha|<g$. Then $P_g(\ip qk)=\ip{\Phi_q(q)}{\Phi_k(k)}$, and both vectors have
$r_g=\binom{d'+g-1}{d'}\le\binom{d'+g}{g}$ coordinates, where $d'\le C\log n+1$ is the dimension after \sref{1}{2}.
\pf The multinomial theorem gives $\ip qk^t/t!=\sum_{|\alpha|=t}\prod_u(q_uk_u)^{\alpha_u}/\alpha_u!$.
\step{1}{6} $r_g\le(eA_0/\gamma_0)\,n^{\eta/2}$ for all large $n$.
\pf $\binom{d'+g}{g}\le(e(d'+g)/g)^g$, and $(d'+g)/g\le((C/\ln2)\ln n+1+\gamma_0\ln n+1)/(\gamma_0\ln n)\le A_0/\gamma_0$ for
large $n$. So $r_g\le(eA_0/\gamma_0)^{\gamma_0\ln n+1}=(eA_0/\gamma_0)\,n^{\gamma_0\ln(eA_0/\gamma_0)}$.
\step{1}{7} \Let the algorithm compute $\Phi_q(q_i)$ and $\Phi_k(k_j)$ for the rounded vectors, then
$U=\sum_j\Phi_k(k_j)v_j^\top$ and $u=\sum_j\Phi_k(k_j)$, and output $\tilde o_i=U^\top\Phi_q(q_i)/\ip{u}{\Phi_q(q_i)}$. It
uses $O(nr_g(d'+d_v))=O(n^{1+\eta})$ arithmetic operations on rationals of $O(\log^2n)$ bits.
\pf Each monomial of degree $t\ge1$ is a monomial of degree $t-1$ times one coordinate, so each vector takes
$O(r_g)$ operations after an $O(r_gd')$ enumeration of the multi-indices; the products and sums take
$O(nr_gd_v)$ operations, and by \sref{1}{6} the total is $O(n^{1+\eta})$. By \sref{1}{3}, a monomial of degree below
$g$ is an integer of $O(g\log n)$ bits divided by $2^{L(g-1)}$; with the common denominator $2^{L(g-1)}(g-1)!$ for
$\Phi_q$, and $2^L$ for the values, every number in the computation has a numerator of
$O(g\log n+\log(nr_g))=O(\log^2n)$ bits.
\qedstep{1}{8}
\pf By \sref{1}{5}, $\ip{u}{\Phi_q(q_i)}=\sum_jP_g(\ell'_{ij})$ and $U^\top\Phi_q(q_i)=\sum_jP_g(\ell'_{ij})v'_j$ for the rounded
logits $\ell'$ and values $v'$, so $\tilde o_i$ is the average of the $v'_j$ with weights $P_g(\ell'_{ij})$. By \sref{1}{4}
these weights are $e^{\ell'_{ij}}$ times factors in $[1-n^{-\beta-2},1+n^{-\beta-2}]$, which moves the average by at most
$3n^{-\beta-2}$, as in \cref{lem:perturb}. With \sref{1}{3}, the total error is at most $3n^{-\beta-2}+4n^{-\beta-3}\le n^{-\beta}$.
\end{steps}
\end{proof}

\subsection{Dimension matters at high precision}\label{app:dimension}

\proppolyhigh*

\begin{proof}
\begin{steps}
\step{1}{1} \Let $\gamma_1=2(\beta+5)/a$, $R=(\log n)^{1-a}+1$ and $g=\lceil\gamma_1\ln n/\ln\ln n\rceil$, and assume $n$ is
large.
\step{1}{2} Steps \sref{1}{2}, \sref{1}{3}, \sref{1}{5}, \sref{1}{7} and \sref{1}{8} of the proof of \cref{thm:poly} hold
with $d'\le(\log n)^C+1$, with $R$ and $g$ as in \sref{1}{1}, with the spread bound $(\log n)^{1-a}$ in place of
$\kappa\ln n$, and with steps \sref{1}{2} and \sref{1}{3} there carried out in the opposite order, provided that
$|P_g(x)/e^x-1|\le n^{-\beta-2}$ for $|x|\le R$ and $r_g\le n^{\eta/2}$.
\pf First every entry of the queries, keys and values is rounded to the nearest multiple of $2^{-L}$, as in step
\sref{1}{3} there; the input entries are rationals of $O(\log n)$ bits, hence at most $n^{K_2}$ in absolute value. A
logit is a sum of at most $(\log n)^C$ products, and $(\log n)^C(2n^{K_2-K_1}+n^{-2K_1})\le n^{-\beta-3}$
for large $n$ when $K_1\ge K_2+\beta+5$; so every logit moves by at most $n^{-\beta-3}$ and every output by at most
$4n^{-\beta-3}$. Then the coordinate $-\ip{\tilde q_i}{\tilde k_1}$ of the rounded vectors is appended to each query and $1$
to each key, as in step \sref{1}{2} there. This coordinate is a multiple of $2^{-2L}$ of absolute value $n^{O(1)}$, the
shift preserves the outputs of the rounded instance, and every shifted logit lies within
$(\log n)^{1-a}+2n^{-\beta-3}\le R$ of $0$. Step \sref{1}{5} holds in every dimension. Step \sref{1}{7} uses
$O(nr_g(d'+d_v))=O(n^{1+\eta/2}(\log n)^C)=O(n^{1+\eta})$ operations; with the grid $2^{-2L}$ in place of $2^{-L}$, a monomial
of degree below $g$ is an integer of $O(g\log n)$ bits divided by $2^{2L(g-1)}$, so every number has
$O(g\log n+\log(nr_g))=O(\log^2n)$ bits. Step \sref{1}{8} uses the Taylor bound of the proviso, the containment of the
shifted rounded logits in $[-R,R]$, and the rounding bound.
\step{1}{3} For $|x|\le R$, $|P_g(x)/e^x-1|\le e^{2R}(eR/g)^g\le n^{-\beta-2}$.
\pf The first inequality is shown in step \sref{1}{4} of the proof of \cref{thm:poly}. Since $a>0$,
$e^{2R}=e^{2(\log n)^{1-a}+2}\le n$ for large $n$. Since $a\le1$, $R\le2(\log n)^{1-a}$, and with $\ln n=\ln2\cdot\log n$,
\[
\frac{g}{eR}\ge\frac{\gamma_1\ln2}{2e}\cdot\frac{(\log n)^a}{\ln\ln n}.
\]
As $\ln\log n\ge\ln\ln n$, this gives $\ln(g/(eR))\ge a\ln\ln n-\ln\ln\ln n+\ln(\gamma_1\ln2/(2e))\ge(a/2)\ln\ln n$ for large
$n$, and so $g\ln(g/(eR))\ge(\gamma_1\ln n/\ln\ln n)(a/2)\ln\ln n=(\beta+5)\ln n$. Hence $(eR/g)^g\le n^{-\beta-5}$ and
$e^{2R}(eR/g)^g\le n^{-\beta-4}$.
\step{1}{4} $r_g\le n^{\eta/2}$.
\pf $r_g=\binom{d'+g-1}{g-1}\le(e(d'+g-1)/(g-1))^{g-1}$. For large $n$, $g-1\ge\gamma_1\ln n/(2\ln\ln n)$ and
$d'\le2(\log n)^C$, so
\[
\frac{d'+g-1}{g-1}=1+\frac{d'}{g-1}\le1+\frac{4(\log n)^C\ln\ln n}{\gamma_1\ln n}\le\Bigl(1+\frac6{\gamma_1}\Bigr)(\log n)^{C-1}\ln\ln n .
\]
With $g-1\le\gamma_1\ln n/\ln\ln n$ and $\ln\log n\le\ln\ln n+1$,
\[
\ln r_g\le\frac{\gamma_1\ln n}{\ln\ln n}\Bigl((C-1)(\ln\ln n+1)+\ln\ln\ln n+1+\ln\bigl(1+6/\gamma_1\bigr)\Bigr)
=\gamma_1(C-1)\ln n+o(\ln n).
\]
Since $\gamma_1(C-1)=2(\beta+5)(C-1)/a<\eta/2$ by the choice of $a$, $r_g\le n^{\eta/2}$ for large $n$.
\qedstep{1}{5}
\pf By \sref{1}{2}, \sref{1}{3} and \sref{1}{4}.
\end{steps}
\end{proof}