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

\factwilliams*

\begin{proof}
\begin{steps}
\step{1}{1} \Let the variables be split into halves $X$ and $Y$. For $x\in\{0,1\}^X$ \Let $a_x\in\{0,1\}^M$
have $a_x[C]=1$ if and only if $x$ satisfies no literal of clause $C$ over $X$; define $b_y$ for
$y\in\{0,1\}^Y$ in the same way.
\step{1}{2} $(x,y)$ satisfies the formula if and only if $\ip{a_x}{b_y}=0$.
\pf $(x,y)$ falsifies $C$ if and only if $x$ satisfies no literal of $C$ over $X$ and $y$ none over $Y$, that is,
$a_x[C]=b_y[C]=1$.
\qedstep{1}{3}
\pf The lists $(a_x)_x$ and $(b_y)_y$ have $2^{N/2}$ entries each, repetitions included, and are computed
in time $2^{N/2}\poly(N,M)$.
\end{steps}
\end{proof}

\subsection{CNF-SETH in polylogarithmic dimension}\label{app:cnfseth}

\thmcnfseth*

\begin{proof}
\begin{steps}
\step{1}{1} \Let $c_0$ be the constant of \cref{hyp:cnfseth} for $\gamma/2$, and $C=c_0+1$. \Assume an algorithm
$\mathcal A$ solves $\ATT(n,\lceil(\log n)^C\rceil,\lceil(\log n)^C\rceil\ln(16n),1/6)$ in time $O(n^{2-\gamma})$.
\Prove CNF formulas with $N$ variables and at most $N^{c_0}$ clauses can be decided in time $O(2^{(1-\gamma/2)N})$.
\step{1}{2} \Let $F$ have $N$ variables, $N$ even after adding a dummy variable, and $M\le N^{c_0}$ clauses, and
\Let $(A,B)$ be the instance of $\OV_{n,M}$ of \cref{fact:williams}, $n=2^{N/2}$. Then $M\le(2\log n)^{c_0}$.
\step{1}{3} \Let $\lambda=\lceil10\ln(14n)\rceil/10$. \Let the instance $I$ have the queries $q_a=(-\lambda a,-11/10)$
for $a\in A$ and one zero query, the keys $k_b=(b,0)$ with value $1$ for $b\in B$, and the key $k^*=(0,1)$
with value $0$. Its size is $n+1$, its dimension $M+1\le\lceil(\log(n+1))^C\rceil$ for large $n$, and its
spread at most $(M+1)\ln(16n)$.
\pf The logits of $q_a$ are $-\lambda\ip ab\in[-\lambda M,0]$ and $-11/10$, and $\lambda M\le M(\ln(14n)+1/10)\le
M\ln(16n)$, as $\ln(16/14)>1/10$. The zero query has all logits $0$. Finally $(2\log n)^{c_0}+1\le(\log n)^{c_0+1}$
for large $n$.
\step{1}{4} If $a$ has an orthogonal partner in $B$, its output is at least $3/4$; otherwise at most $1/4$.
\pf The output is $S_a/(S_a+e^{-11/10})$ with $S_a=\sum_be^{-\lambda\ip ab}$. An orthogonal partner gives
$S_a\ge1$ and output at least $1/(1+e^{-11/10})>3/4$. Otherwise $S_a\le ne^{-\lambda}\le ne^{-\ln(14n)}$, and the
output is at most $S_ae^{11/10}\le e^{11/10}/14<1/4$.
\qedstep{1}{5}
\pf Run $\mathcal A$ once on $I$ and answer YES if and only if some $q_a$ receives an output above $1/2$. By
\sref{1}{4} and \cref{fact:williams} the answer is correct with probability at least $2/3$. The time is
$2^{N/2}\poly(N)+O((n+1)^{2-\gamma})=O(2^{(1-\gamma/2)N})$, contradicting the choice of $c_0$.
\end{steps}
\end{proof}

\subsection{Clause exponent below two}\label{app:below-two}

\lemmagap*

\begin{proof}
\begin{steps}
\step{1}{1} Pad Merlin's proof, the coins and Bob's message of the protocol of \cref{fact:rub} to exactly $p$,
$\rho$ and $\ell$ bits, and \Let $\nu(b,w)$ be Bob's message on input $b$ and coins $w$. \Let the $k$-fold protocol
use coins $w=(w_1,\dots,w_k)\in\{0,1\}^{k\rho}$, \Let Bob send $\nu_k(b,w)=(\nu(b,w_1),\dots,\nu(b,w_k))$, and \Let
Alice accept on proof $\mu$ if and only if she accepts every pair $(w_i,\nu(b,w_i))$ in the original protocol. Then disjoint inputs have a proof that is
accepted for all coins, and for intersecting inputs every proof is accepted with probability at most
$2^{-k}$.
\pf Unused coins do not change acceptance probabilities. For a fixed proof, the $k$ checks use independent
coins, so the acceptance probabilities multiply.
\step{1}{2} For $\mu\in\{0,1\}^p$ and $a\in A$ \Let $x_{\mu,a}\in\{0,1\}^{\{0,1\}^{k\rho}\times\{0,1\}^{k\ell}}$
have $x_{\mu,a}[w,\zeta]=1$ if and only if Alice accepts on input $a$, proof $\mu$, coins $w$ and message
$\zeta$. For $b\in B$ \Let $y_b[w,\zeta]=1$ if and only if $\zeta=\nu_k(b,w)$. Instance $\mu$ is
$((x_{\mu,a})_{a\in A},(y_b)_{b\in B})$.
\step{1}{3} $\ip{x_{\mu,a}}{y_b}$ equals the number of coin strings $w$ on which Alice accepts $a$, $b$ and $\mu$.
\pf For each $w$, the vector $y_b$ has exactly one $1$ in block $w$, at $\zeta=\nu_k(b,w)$.
\qedstep{1}{4}
\pf By \sref{1}{3}, every inner product is an integer in $[0,2^{k\rho}]$, which is (i). By \sref{1}{1}, an
orthogonal pair $(a,b)$ has a proof $\mu$ with inner product $2^{k\rho}$, which is (ii), and if there is no
orthogonal pair every inner product is at most $2^{-k}2^{k\rho}$, which is (iii). Each of the
$2^{k(\rho+\ell)}$ coordinates of each of the $(2^p+1)n$ vectors needs $k$ evaluations of the protocol's predicates,
each computable in time $\poly(m)$.
\end{steps}
\end{proof}

\thmbelowtwo*

\begin{proof}
\begin{steps}
\step{1}{1} \Let $D=\lceil(2\log n)^{c_0}\rceil$. Then $\OV_{n,D}$ cannot be solved in time $O(n^{2-\gamma/2})$.
\pf An algorithm in time $O(n^{2-\gamma/2})$ would decide CNF formulas with $N$ variables and at most $N^{c_0}$
clauses in time $O(2^{(1-\gamma/4)N})$ by \cref{fact:williams}, contradicting
$\mathrm{CNF\text{-}SETH}_{c_0}$ for $\gamma/4$.
\step{1}{2} \Let $k=\lceil\log(4/\theta)\rceil$ and $s=\lceil8a_1D\log D/(\gamma\log n)\rceil$. For large $n$,
$2\le s\le D$, Merlin's proof has $p\le(\gamma/8)\log n$ bits, and $k(\rho+\ell)\le K_0(\log n)^{c_0-1}(\log\log n)^2$
for a constant $K_0$ depending on $\gamma$, $\theta$ and $c_0$.
\pf $D\ge2\log n$, so $D\log D/\log n\to\infty$ and $\log D=O(\log\log n)$; hence $2\le s\le D$ for large $n$. By
\cref{fact:rub}, $p\le a_1(D/s)\log s\le(\gamma\log n/(8\log D))\log s\le(\gamma/8)\log n$. Also
$\rho\le a_2\log D$ and $\ell\le a_3s\log s=O(D\log^2D/(\gamma\log n))=O((\log n)^{c_0-1}(\log\log n)^2/\gamma)$.
\step{1}{3} \Let $K=K_0+1$. For each of the $2^p$ instances of \cref{lem:magap} with these parameters, build
the attention instance of step \sref{1}{3} in the proof of \cref{thm:ldovlb}, with $T_k$ in place of $T$ and
$2^k$ in place of $\tau$. It has $n+1$ queries and keys, dimension $2^{k(\rho+\ell)}+1\le d(n+1)$, all logits in
$[0,\lambda T_k]$ with $\lambda T_k\le(1+\theta)\ln n$ for large $n$, and a query $q_x$ has output at least $1-\eta$
if $x$ has a partner at inner product $T_k$ and at most $\eta$ if all its inner products are at most
$2^{-k}T_k$, where $\eta=(1-2\eps)/4$.
\pf Steps \sref{1}{4} and \sref{1}{5} of that proof use only that all inner products lie in $[0,T]$, that an instance
has at most $n$ real keys, and that $1/\tau\le\theta/4$; these hold with $T_k$ and $\tau=2^k\ge4/\theta$ by
\cref{lem:magap}(i).
\step{1}{4} \Assume an algorithm $\mathcal A$ solves $\ATT(n,d(n),(1+\theta)\ln n,\eps)$ in time $O(n^{2-\gamma})$.
Then $\OV_{n,D}$ can be solved in time $O(n^{2-\gamma/2})$.
\pf As in step \sref{1}{6} of the proof of \cref{thm:ldovlb}, with $N_\psi=2^p\le n^{\gamma/8}$ instances and
$R=\lceil18\ln(3\cdot2^p)\rceil$ runs each; that step uses the two implications of its step \sref{1}{5}, which hold here
by \sref{1}{3}, and items (ii) and (iii) of \cref{fact:chen}, which hold here by \cref{lem:magap}(ii) and (iii). The calls take $2^pR\cdot O((n+1)^{2-\gamma})=O(n^{2-7\gamma/8}\log n)$,
and \cref{lem:magap} takes $2^{p+k(\rho+\ell)}nk\poly(D)=n^{1+\gamma/8+o(1)}$, since $c_0<2$ makes
$k(\rho+\ell)=o(\log n)$.
\qedstep{1}{5}
\pf \sref{1}{4} contradicts \sref{1}{1}. Finally $d(n)=n^{o(1)}$ because $(\log n)^{c_0-1}(\log\log n)^2=o(\log n)$ for
$c_0<2$.
\end{steps}
\end{proof}

\subsection{A barrier for the bounded-entry threshold}\label{app:barrier}

The barrier rests on the following tradeoff for Merlin--Arthur protocols, which is Klauck's
argument~\cite[Theorem~1, part~1]{Kla03} with the proof length and the communication kept apart. In a
\emph{public-coin MA protocol} for a function $f$, Merlin sends a proof $z\in\{0,1\}^{c_M}$ to both players, who
then run a public-coin randomized protocol whose transcript has at most $c_P\ge1$ bits and determines the
output. The protocol computes $f$ with error $1/4$ if every input with $f=1$ has a proof accepted with
probability at least $3/4$, and every input with $f=0$ is accepted with probability at most $1/4$ under every
proof. The one-message protocols of \cref{sec:imported} are of this form after Alice announces her decision.

\begin{lemma}[Klauck's tradeoff]\label[lemma]{lem:klauck}
There is an absolute constant $\alpha_0\in(0,1]$ such that every public-coin MA protocol computing
$\DISJ_D$ with error $1/4$ satisfies $(c_M+1)\,c_P\ge\alpha_0D$.
\end{lemma}

\begin{proof}
\begin{steps}
\step{1}{1} \Let $\alpha_1,\eps_1,\mu$ be as in \cref{fact:razborov}, with $\alpha_1\le1$ without loss of
generality, \Let $\mu_1$ and $\mu_0$ be $\mu$ conditioned on $\DISJ_D^{-1}(1)$ and on $\DISJ_D^{-1}(0)$,
and \Let $\eta=\alpha_12^{-c_M}/16$.
\step{1}{2} \Let $t=\lceil8(c_M+\log(16/\alpha_1))\rceil$. Repeating the randomized part $t$ times with fresh
coins and taking the majority gives, for every fixed proof, a protocol with transcripts of at most
$k=tc_P$ bits whose acceptance probability is at least $1-\eta$ when the original one is at least $3/4$, and at
most $\eta$ when the original one is at most $1/4$.
\pf By Hoeffding's inequality, the majority of $t$ independent runs errs with probability at most
$e^{-t/8}\le\eta$, because $t/8\ge c_M\ln2+\ln(16/\alpha_1)$. The $t$ transcripts determine the majority.
\step{1}{3} There are a proof $z^*$ and a set $G\subseteq\DISJ_D^{-1}(1)$ with $\mu_1(G)\ge2^{-c_M}$ such that the
protocol of \sref{1}{2} with proof $z^*$ accepts every input of $G$ with probability at least $1-\eta$.
\pf Assign to every disjoint input a proof accepted with probability at least $3/4$. One of the at most
$2^{c_M}$ proofs receives $\mu_1$-mass at least $2^{-c_M}$.
\step{1}{4} There is a coin string such that the resulting deterministic protocol, with accepting set
$\mathrm{Acc}$, satisfies $\mu_1(G\cap\mathrm{Acc})\ge\mu_1(G)/4$ and
$\mu_0(\mathrm{Acc})\le2\eta\,\mu_1(G\cap\mathrm{Acc})/\mu_1(G)$.
\pf Over the coins, $\mathbb E[\mu_1(G\cap\mathrm{Acc})]\ge(1-\eta)\mu_1(G)$ by \sref{1}{3}, and
$\mathbb E[\mu_0(\mathrm{Acc})]\le\eta$ by \sref{1}{2} and soundness. So
$Y=\mu_1(G\cap\mathrm{Acc})-\frac{\mu_1(G)}{2\eta}\mu_0(\mathrm{Acc})$ has
$\mathbb EY\ge(\frac12-\eta)\mu_1(G)\ge\mu_1(G)/4$, and some coin string has $Y\ge\mu_1(G)/4$. Both claims
follow, as $\mu_0(\mathrm{Acc})\ge0$.
\step{1}{5} $k\ge\eps_1D-c_M-\log(8/\alpha_1)$.
\begin{steps}
\step{2}{1} $\mathrm{Acc}$ is the disjoint union of at most $2^k$ rectangles.
\pf The inputs with a given transcript form a rectangle, and the transcript determines the output.
\step{2}{2} $\frac14\mu_0(\mathrm{Acc})\ge\frac34\alpha_1\,\mu_1(G\cap\mathrm{Acc})-2^{k-\eps_1D}$.
\pf Apply \cref{fact:razborov} to each rectangle of \sref{2}{1} and add, using
$\mu(\cdot\cap\DISJ_D^{-1}(0))=\frac14\mu_0$, $\mu(\cdot\cap\DISJ_D^{-1}(1))=\frac34\mu_1$ and
$\mu_1(\mathrm{Acc})\ge\mu_1(G\cap\mathrm{Acc})$.
\qedstep{2}{3}
\pf By \sref{1}{4}, $\frac14\mu_0(\mathrm{Acc})\le\frac{\eta}{2\mu_1(G)}\mu_1(G\cap\mathrm{Acc})\le
\frac{\alpha_1}{32}\mu_1(G\cap\mathrm{Acc})$, since $\eta\le\alpha_1\mu_1(G)/16$. With \sref{2}{2},
$2^{k-\eps_1D}\ge(\frac34-\frac1{32})\alpha_1\mu_1(G\cap\mathrm{Acc})\ge\frac{\alpha_1}{8}\mu_1(G)\ge
\frac{\alpha_1}{8}2^{-c_M}$.
\end{steps}
\qedstep{1}{6}
\pf \Let $K_1=8\log(16/\alpha_1)+9$ and $K_2=\log(8/\alpha_1)$, so that $k\le(8c_M+K_1)c_P$ and
$(8c_M+K_1)c_P\ge\eps_1D-c_M-K_2$ by \sref{1}{5}. If $c_M\ge\eps_1D/4$, then $(c_M+1)c_P\ge c_M\ge\eps_1D/4$, as
$c_P\ge1$. If $D<4K_2/\eps_1$, then $(c_M+1)c_P\ge1>\eps_1D/(4K_2)$. Otherwise $\eps_1D-c_M-K_2\ge\eps_1D/2$, and
$(c_M+1)c_P\ge(8c_M+K_1)c_P/K_1\ge\eps_1D/(2K_1)$, because $K_1\ge8$. Take
$\alpha_0=\min\{\eps_1/4,\eps_1/(4K_2),\eps_1/(2K_1),1\}$.
\end{steps}
\end{proof}

\thmbarrier*

\begin{proof}
\begin{steps}
\step{1}{1} \Let $Q_2=\max\|q(\mu,a)\|_2$ and $K_2=\max\|k(\mu,b)\|_2$, so that $\sigma=Q_2K_2$. Every logit
$\ip{q(\mu,a)}{k(\mu,b)}$ lies in $[-\sigma,\sigma]$, and $\Delta\le2\sigma$; in particular $\sigma>0$ and
$\Gamma\ge1/2$.
\pf $|\ip qk|\le\|q\|_2\|k\|_2\le\sigma$. With $e_1$ the first unit vector, (G1) for the disjoint pair
$(e_1,0)$ gives $\mu$ with $\ip{q(\mu,e_1)}{k(\mu,0)}\ge h(\mu,e_1)$, and (G2) for the intersecting pair
$(e_1,e_1)$ gives $\ip{q(\mu,e_1)}{k(\mu,e_1)}\le h(\mu,e_1)-\Delta$ for the same $\mu$. Two logits in
$[-\sigma,\sigma]$ differ by at least $\Delta$.
\step{1}{2} \Let $u=\lceil384\,\Gamma^2\rceil$, $t_0=\sqrt{2\ln(32u)}$ and $\ell_0=\lceil\log(8t_0^2\Gamma)\rceil$. \Let the MA
protocol for $\DISJ_D$ on inputs $a,b$ be: Merlin sends $\mu$; public coins pick independent uniform
$s_1,\dots,s_u\in\{-1,1\}^d$; for each $i$ Bob sends the integer $\hat k_i$ nearest to $2^{\ell_0}Y_i/(t_0K_2)$, where $Y_i$ is
$\ip{s_i}{k(\mu,b)}$ clamped to $[-t_0K_2,t_0K_2]$; Alice computes
$Z=\frac1u\sum_i\ip{s_i}{q(\mu,a)}\,t_0K_22^{-\ell_0}\hat k_i$ and sends $1$ if and only if $Z\ge h(\mu,a)-\Delta/2$. It
computes $\DISJ_D$ with error $1/4$, with $c_M=p$ and $c_P\le3885\,\Gamma^2\log(2+\Gamma)$.
\begin{steps}
\step{2}{1} \Let $q=q(\mu,a)$, $k=k(\mu,b)$ and $X_i=\ip{s_i}q\ip{s_i}k$. The $X_i$ are independent, have mean $\ip qk$,
and satisfy $\mathbb EX_i^2\le3\sigma^2$.
\pf $\mathbb E[s_is_i^\top]$ is the identity, which gives the mean. For uniform $s\in\{-1,1\}^d$ and $x\in\R^d$,
$\mathbb E\ip sx^4=3\|x\|_2^4-2\sum_tx_t^4\le3\|x\|_2^4$, so by the Cauchy--Schwarz inequality
$\mathbb EX_i^2\le(\mathbb E\ip{s_i}q^4\,\mathbb E\ip{s_i}k^4)^{1/2}\le3\|q\|_2^2\|k\|_2^2\le3\sigma^2$.
\step{2}{2} With probability at least $3/4$, $\bigl|\frac1u\sum_iX_i-\ip qk\bigr|<\Delta/4$, and
$|\ip{s_i}q|\le t_0Q_2$ and $|\ip{s_i}k|\le t_0K_2$ for all $i$.
\pf By Chebyshev's inequality and \sref{2}{1}, the first condition fails with probability at most
$3\sigma^2/(u(\Delta/4)^2)=48\Gamma^2/u\le1/8$. By Hoeffding's inequality, $\Pr[|\ip sx|>t_0\|x\|_2]\le2e^{-t_0^2/2}=1/(16u)$
for each of the $2u$ sums, and a union bound gives $1/8$.
\step{2}{3} On the event of \sref{2}{2}, $|Z-\ip qk|<\Delta/2$.
\pf No clamping occurs. So the $i$th term of $Z$ differs from $X_i$ by at most
\[
|\ip{s_i}q|\cdot t_0K_2\,2^{-\ell_0-1}\le t_0^2\sigma\,2^{-\ell_0-1}\le\Delta/16,
\]
because $2^{\ell_0}\ge8t_0^2\Gamma$ and $\sigma/\Gamma=\Delta$. Hence $|Z-\ip qk|<\Delta/4+\Delta/16$.
\step{2}{4} Completeness and soundness hold with error $1/4$.
\pf If $\ip ab=0$, (G1) gives $\mu$ with $\ip qk\ge h(\mu,a)$, and by \sref{2}{2} and \sref{2}{3} Alice accepts with
probability at least $3/4$. If $\ip ab\ge1$, every $\mu$ has $\ip qk\le h(\mu,a)-\Delta$ by (G2), and Alice accepts
with probability at most $1/4$. Alice knows $h(\mu,a)$, $\Delta$, $t_0$, $\ell_0$ and $K_2$.
\step{2}{5} $c_P\le3885\,\Gamma^2\log(2+\Gamma)$.
\pf Each $\hat k_i$ is an integer in $[-2^{\ell_0},2^{\ell_0}]$ and takes at most $\ell_0+2\le\log(64t_0^2\Gamma)$ bits, and
$c_P\le u(\ell_0+2)+1$. As $\Gamma\ge1/2$, $u\le388\Gamma^2$ and $t_0^2\le2\ln(12416\Gamma^2)$, so
$64t_0^2\Gamma\le256\Gamma\ln(112\Gamma)\le(103\Gamma)^2$, using $\ln y\le y/e$. Hence
$c_P\le776\Gamma^2\log(103\Gamma)+1\le777\Gamma^2\log(103\Gamma)$, as $\Gamma^2\log(103\Gamma)\ge1$. Finally
$\log(103\Gamma)\le5\log(2+\Gamma)$, because $(2+\Gamma)^5/\Gamma$ is smallest at $\Gamma=1/2$, where it exceeds $103$.
\end{steps}
\step{1}{3} $c_P\ge\alpha_0D/(p+1)$.
\pf By \cref{lem:klauck} with $c_M=p$.
\qedstep{1}{4}
\pf By \sref{1}{2} and \sref{1}{3}, $3885\Gamma^2\log(2+\Gamma)\ge\alpha_0D/(p+1)$. Take $\alpha_2=\alpha_0/3885$.
\end{steps}
\end{proof}