\documentclass[11pt]{article}
\pdfsuppressptexinfo=-1
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs,array}
\usepackage[hidelinks]{hyperref}
\hypersetup{pdftitle={Which Fine-Grained Lower Bounds Survive the Refutation of 3SUM and APSP?},pdfauthor={Tejasvi Singh Tomar}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{hypothesis}[theorem]{Hypothesis}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\LST}{\mathrm{LST}}
\newcommand{\eps}{\varepsilon}
\newcommand{\epsex}{\varepsilon^{\mathrm{ex}}}
\renewcommand{\topfraction}{0.95}\renewcommand{\bottomfraction}{0.8}\renewcommand{\textfraction}{0.05}\renewcommand{\floatpagefraction}{0.75}

\title{Which Fine-Grained Lower Bounds Survive the Refutation of 3SUM and APSP?}
\author{Tejasvi Singh Tomar}
\date{Version 4, 27 October 2026}

\begin{document}
\maketitle

\begin{abstract}
Alman and Vassilevska Williams have refuted the 3SUM and APSP hypotheses. Their algorithms rest on counting the triangles through prescribed edges of lopsided tripartite graphs, whose middle part has $n^{\eps}$ vertices for a small $\eps$. Majdoddin extended the method to every $\eps<\ln4/(5\ln5)\approx0.172$. We determine which of the main conditional lower bounds derived from the refuted hypotheses survive. We also prove that the method extends to every $\eps<0.17843$ when the prescribed edges are known in advance and there are at most $n^{2-\eps/2}$ of them, which confirms Majdoddin's numerical estimate. Whether a bound survives depends mostly on the instances that its reduction produces. The reductions behind most bounds produce instances outside the range of the new algorithms: balanced graphs, or lopsided graphs with a larger middle part. Most of the set-disjointness, dynamic-graph and triangle bounds therefore follow from hypotheses that no known algorithm contradicts. These hypotheses, however, concern mainly such instances, and for several bounds the hypothesis is the bound itself, stated for these instances. Their evidence came largely from the refuted hypotheses. A few bounds are false, among them a lower bound of Goldstein, Lewenstein and Porat for Set Disjointness over small universes; the Strong SetDisjointness Conjecture also fails at small polynomial query times. Other bounds have lost their support, such as the Set Disjointness trade-offs of Kopelowitz, Pettie and Porat over small universes apart from constant query time. Finally, we collect the known obstacles to a larger closed-form range with a different base identity and use border-rank lower bounds to exclude several natural candidates.
\end{abstract}

\section{Introduction}

For two decades the 3SUM and APSP hypotheses, together with SETH and OMv, were the main sources of conditional lower bounds in fine-grained complexity. Alman and Vassilevska Williams~\cite{AV26} recently refuted both. Their deterministic algorithms solve 3SUM on integers of polynomial magnitude in $O(n^{1.9992})$ time and APSP with polynomially bounded integer weights in $O(n^{2.99942})$ time, and their core algorithm, composed with known reductions, also refutes the Exact Triangle, weighted $k$-Clique, $(\min,+)$-convolution and Directed Unweighted APSP hypotheses; the same approach solves 3XOR in truly subquadratic time~\cite[Remark 23]{AV26},~\cite{Maj26}. Majdoddin~\cite{Maj26} improved the exponents (Section~\ref{sec:status}). Simpler algorithms and proofs~\cite{SY26,KL26} and a reduction from real to integer 3SUM~\cite{FPS26} also appeared.

A lower bound derived from a refuted hypothesis remains a true implication, but it no longer gives evidence for the bound. For each of the main bounds we determine, often separately for different ranges of its parameters, which of three cases holds: a known algorithm now beats it, so it is false; it follows from another hypothesis that no known algorithm contradicts, which we call a \emph{surviving} hypothesis; or no surviving hypothesis is known to imply it, and it has lost its evidence. Section~\ref{sec:survive} refines these cases into five verdicts.

\paragraph{Where the new algorithms work.} At the core of~\cite{AV26} is an algorithm that computes prescribed entries of a thin matrix product $XY$ with $X\in\mathbb Z^{N\times D}$ and $D\le N^{\eps}$. In graph terms, it counts the triangles through prescribed edges of a tripartite graph whose middle part has only $N^{\eps}$ vertices. Majdoddin extended the range of this matrix theorem from $\eps<0.1204$ to every $\eps<\eps^*:=\ln4/(5\ln5)=0.17227\ldots$, the exponent of Coppersmith's rectangular matrix multiplication algorithm from Schönhage's partial-product tensor~\cite{Cop82}. Alman and Vassilevska Williams note that the reductions of Kopelowitz, Pettie and Porat~\cite{KPP16} and of Vassilevska Williams and Xu~\cite[Corollary 3.12]{VX20a} produce instances of this lopsided kind~\cite[Section 3.1]{AV26}. Most downstream reductions, however, produce instances outside the range of the algorithms: balanced graphs, or lopsided graphs whose middle part is larger. The shape of the instances behind a bound therefore largely decides its fate, and much of the classification reduces to determining that shape. In Section~\ref{sec:lst} we parametrize the lopsided instances by the exponent $\delta$ of the size of the middle part, state a hypothesis $\mathrm{LSTH}_\delta$ for the natural instances that the reductions produce, and state, under the name $\mathrm{BST}$, the hypothesis of~\cite[Section 6]{AV26} that the balanced case needs $m^{4/3-o(1)}$ time, together with the related forms that some downstream reductions need.

\paragraph{Verdicts.} Table~\ref{tab:status} gives the status of the standard hypotheses, and Tables~\ref{tab:survive1} and~\ref{tab:survive2} give the verdicts for the main conditional lower bounds; Section~\ref{sec:survive} gives the reasons. Alman and Vassilevska Williams already mark the problems reached from 3SUM, APSP or Exact Triangle only by one-way reductions as having lost their evidence~\cite[Figure 1]{AV26}. We find that most set-disjointness, dynamic-graph and triangle bounds follow from surviving hypotheses, mostly hypotheses about the instances that the reductions produce, and for some dynamic and data-structure bounds the OMv conjecture or the part of the Strong SetDisjointness Conjecture that survives. The hypotheses about instances are not contradicted by any known algorithm, but their evidence came largely from the refuted hypotheses (Table~\ref{tab:status} marks them open, and $\mathrm{LSTH}_\delta$ as refuted in a regime), and for several bounds the hypothesis is the bound itself, stated for those instances. An exception is the triangle-detection hypothesis of~\cite[Corollary 1.11]{ABKZ22}, which was never derived from 3SUM or APSP and which implies $\mathrm{BST}$, its degree-bounded form for degree $\sqrt n$ and the all-nodes form; the evidence offered for it uses a regime that the refutation is not known to affect (Section~\ref{sec:tri}). The data structure of~\cite{AV26,Maj26} itself makes a few bounds false: a lower bound of Goldstein, Lewenstein and Porat for Set Disjointness, at universe sizes $m^r$ with $r<\eps^*$ (Proposition~\ref{prop:glp}), and, for small polynomial query times, the Strong SetDisjointness Conjecture of~\cite{GKLP17b} (Corollary~\ref{cor:ssd}). Other bounds have lost their support, such as the Set Disjointness trade-offs of~\cite{KPP16} where they use universes below $n^{\eps^*}$, except at constant query time (Proposition~\ref{prop:kpp}), and the quadratic bounds for most 3SUM-hard problems in computational geometry~\cite{GO95,King04}. The same data structure gives 3SUM-Indexing a randomized data structure with truly subquadratic preprocessing time and truly sublinear expected query time (Proposition~\ref{prop:3sumindexing}).

\paragraph{Queries known in advance.} Majdoddin also reported a numerical evaluation: when the prescribed entries are known in advance, an exact count of the leaves of the recursion takes the method to about $0.1784$~\cite[Section 8]{Maj26}. We prove that it does: for every $\eps$ below an explicit constant $\epsex=0.17843\ldots$ there is $\gamma>0$ such that, for integer matrices $X\in\mathbb Z^{N\times D}$ and $Y\in\mathbb Z^{D\times N}$ with entries of polynomial magnitude and $2\le D\le N^{\eps}$, the entries of $XY$ at any set of at most $N^2/\sqrt D$ positions given in advance can be computed deterministically in $O(N^2/D^{\gamma})$ time (Theorem~\ref{thm:exact}). This is as many positions as the reductions produce. The proof uses Majdoddin's count of the leaves of the pruned recursion~\cite[Lemma 6.1]{Maj26} as it stands, without the split that confines the analysis of~\cite{Maj26} to $\eps<\eps^*$ (Section~\ref{sec:exact}). Consequently $\mathrm{LSTH}_\delta$ is false for every $\delta<\epsex$, and the thresholds of the offline bounds move from $\eps^*$ to $\epsex$; the theorem gives no explicit saving and does not by itself improve the exponents for 3SUM or APSP. For data structures that answer queries online the best known threshold remains $\eps^*$.

\paragraph{The threshold.} The threshold $\eps^*$ is where the analysis of~\cite{Maj26} stops for the five-term partial-product tensor. In Section~\ref{sec:evidence} we collect the known obstacles to a larger range of this analysis with a different base identity, mostly Majdoddin's barriers~\cite[Appendix A]{Maj26}, and add Koszul-flattening lower bounds on border rank that exclude further natural kinds of base identity, among them two that would compute two disjoint inner products at once. The paper thus has two parts: the classification in Sections~\ref{sec:status}--\ref{sec:survive}, and the results on the method itself in Sections~\ref{sec:exact} and~\ref{sec:evidence}. Section~\ref{sec:open} collects open questions.

\section{Hypotheses after the refutation}\label{sec:status}

In Table~\ref{tab:status} we list the standard hypotheses of fine-grained complexity. A hypothesis is \emph{refuted} if a polynomially faster algorithm is known for its problem in the stated form, \emph{refuted in a regime} if this holds for some but not all of its parameters, \emph{open} if the new algorithms do not address it although its evidence came from the refuted hypotheses, and \emph{unaffected} otherwise.

\begin{table}[!tbp]
\centering\small
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{@{}>{\raggedright}p{0.40\linewidth}>{\raggedright}p{0.14\linewidth}>{\raggedright\arraybackslash}p{0.39\linewidth}@{}}
\toprule
Hypothesis & Status & Reference\\
\midrule
3SUM, integers of polynomial magnitude; Strong 3SUM (integers in $[-n^2,n^2]$) & refuted & \cite{AV26,Maj26}\\
3SUM and Exact Triangle over the reals & refuted & real RAM, Las Vegas~\cite[Theorem 35]{AV26}, through~\cite{CVX22}; for 3SUM also~\cite{FPS26}\\
APSP and its subcubic equivalence class~\cite{VW18,AGV15} & refuted & \cite{AV26,Maj26,SY26}\\
Exact Triangle; Strong Exact Triangle (weights in $[-n,n]$)~\cite{CX24} & refuted & \cite[Theorem 19]{AV26}\\
3XOR; 3SUM over $\mathbb F_p^d$ and over abelian groups of exponent $p^2$ & refuted & \cite[Remark 23]{AV26},~\cite[Theorem E, Section 19]{Maj26}\\
Zero-, Min- and Max-Weight $k$-Clique & refuted & \cite[Corollary 39]{AV26}\\
$(\min,+)$-convolution~\cite{KPS17,CMWW19} & refuted & \cite{AV26}, through~\cite{BCD14,BIS17,CMWW19}\\
Directed Unweighted APSP & refuted & \cite[Theorem 34]{AV26}\\
Hinted OMv~\cite[Conjectures 5.2, 5.7, 5.12]{BNS19} & refuted in a regime & thin hints: $\tau<0.1204$~\cite[Corollary 40]{AV26}, $\tau<\eps^*$~\cite[Corollary 10.1, Proposition 10.3]{Maj26}\\
Strong SetDisjointness~\cite[Conjecture 3]{GKLP17b} & refuted in a regime & query time $N^{\tau}$, $0<\tau<\eps^*/(2+\eps^*)=0.0793\ldots$ (Corollary~\ref{cor:ssd})\\
Lopsided Sparse Triangle $\mathrm{LSTH}_\delta$ & refuted in a regime & $\delta<\epsex$ (Corollary~\ref{cor:exact})\\
\midrule
SETH, Orthogonal Vectors & unaffected & \\
OMv without hints~\cite{HKNS15} & unaffected & \\
$k$-SUM and $k$-XOR for $k\ge4$ & unaffected & \cite[Section 1.2]{AV26}\\
3SUM-Indexing (no truly subquadratic space with $\tilde O(1)$ query time) & unaffected & \cite[Section 1.2]{AV26}; the strong form fell in 2019~\cite{KP19,GGHPV20}\\
Multiphase conjecture~\cite{Pat10} & open & its 3SUM-based case follows from $\mathrm{LSTH}_{0.4}$ (Lemma~\ref{lem:fewer}, Section~\ref{sec:sets})\\
$\mathrm{BST}$, its degree-bounded, all-nodes and batched forms, TLH, $\mathrm{LST}(r,\sigma,\kappa)$, $\mathrm{LSTL}$ & open & Section~\ref{sec:lst}; $\mathrm{BST}$, $\mathrm{BST}_{1/2}$ and the all-nodes form also follow from the hypothesis of~\cite[Corollary 1.11]{ABKZ22} (Section~\ref{sec:tri})\\
Combinatorial BMM & unaffected & \\
Combinatorial versions of 3SUM and APSP & open & the new algorithms are algebraic~\cite[Section 1.2]{AV26}\\
\bottomrule
\end{tabular}
\caption{Status of fine-grained hypotheses. Integer inputs have polynomial magnitude and the integer algorithms are deterministic. $\eps^*=\ln4/(5\ln5)=0.17227\ldots$ and $\epsex=0.17843\ldots$ (Section~\ref{sec:exact}).}
\label{tab:status}
\end{table}

For orientation, the best exponents claimed in research papers are $1.9945+o(1)$ for 3SUM and $2.9945+o(1)$ for Exact Triangle, the $(\min,+)$-product and APSP, all deterministic~\cite[Corollary 16.1]{Maj26}, where the $o(1)$ hides a factor $\exp(O(\sqrt{\log n\log\log n}))$~\cite[Sections 13.6, 15.5]{Maj26}, so that the gain over~\cite{AV26} from the second part of~\cite{Maj26} appears only for astronomically large $n$~\cite[Sections 13.7, 15.7]{Maj26}. Saha and Ye give $\tilde O(n^{2.9964})$ for the $(\min,+)$-product and APSP~\cite{SY26}, and an unrefereed repository~\cite{Shr26} claims smaller exponents.
\section{Sparse triangle hypotheses}\label{sec:lst}

Most downstream bounds were derived from the refuted hypotheses through All-Edges Sparse Triangle or offline Set Disjointness, on instances of a particular shape. In this section we state the forms of these problems that the downstream reductions use, determine which of them lie in the range of the new algorithms, and name the rest.

\subsection{Lopsided instances}

\begin{definition}[Lopsided All-Edges Sparse Triangle]
An instance of $\LST(n,u,Q)$ is a tripartite graph with parts $A$ and $B$ of $n$ vertices each and a middle part $M$ of $u$ vertices, arbitrary edges in $A\times M$ and $M\times B$, and a set $W\subseteq A\times B$ of $Q$ query pairs. The task is to decide, for every $(a,b)\in W$, whether $a$ and $b$ have a common neighbour in $M$. In the counting version the task is to output the number of common neighbours.
\end{definition}

In the language of sets, $\LST(n,u,Q)$ is offline Set Disjointness with $n$ sets on each side over a universe of size $u$ and $Q$ queries, and the counting version asks for the sizes of the intersections. Answering each query by merging the two neighbourhoods takes $O(Q\Delta)$ time, where $\Delta$ is the largest degree into $M$. Computing the whole Boolean product of the two biadjacency matrices takes $n^{\omega(1,\log_nu,1)+o(1)}$ time, which is $n^{2+o(1)}$ when $u\le n^{0.321}$~\cite{VXXZ24}.

\begin{definition}[Natural instances]\label{def:natural}
For $0<\delta<2$, a \emph{natural} instance of $\LST_\delta(n)$ is an instance of $\LST(n,n^{\delta},Q)$ in which every vertex of $A\cup B$ has at most $n^{\delta/2}$ neighbours in $M$ and $Q\le n^{2-\delta/2}$.
\end{definition}

Merging solves natural instances in $O(n^{2})$ time for every $\delta$.

\begin{hypothesis}[$\mathrm{LSTH}_\delta$]
For every $\eps>0$, natural instances of $\LST_\delta(n)$ cannot be solved in $O(n^{2-\eps})$ time. The counting form $\#\mathrm{LSTH}_\delta$ is the same statement for the counting version.
\end{hypothesis}

The reductions of~\cite[Theorem 1.4]{KPP16} from 3SUM, of~\cite[Theorem 1.4]{FKP24} from deterministic 3SUM and of~\cite[Corollary 3.12]{VX20a} from Exact Triangle produce, for a parameter $0<\gamma<1$, offline Set Disjointness with $\tilde O(N)$ sets of size $O(N^{1-\gamma})$ over a universe of size $O(N^{2-2\gamma})$ and $\tilde O(N^{1+\gamma})$ queries, where $N$ is the number of sets up to logarithmic factors. After padding the instance with isolated vertices to absorb the logarithmic factors, these are natural instances of $\LST_{2-2\gamma}$. This is the regime pointed out in~\cite[Section 3.1]{AV26}. Consequently 3SUM and Exact Triangle each imply $\mathrm{LSTH}_\delta$ for every $0<\delta<2$, under randomized reductions (deterministic ones for 3SUM, by~\cite{FKP24}). The refutation, however, reaches only small $\delta$.

\begin{theorem}[\cite{AV26,Maj26}]\label{thm:refuted}
For every $\delta<\eps^*$ and every $\mu>0$ there is $\gamma>0$ such that the counting version of $\LST(n,n^{\delta},n^{2-\mu\delta})$ can be solved deterministically in $O(n^{2-\gamma\delta})$ time. In particular $\mathrm{LSTH}_\delta$ and $\#\mathrm{LSTH}_\delta$ are false for every $\delta<\eps^*$.
\end{theorem}

\begin{proof}
Majdoddin's Theorem 7.4, which is part of his Theorem A~\cite{Maj26}, computes the entries of a product $XY$ with $X\in\mathbb Z^{N\times D}$ at any $N^2/D^{\mu}$ prescribed positions in $O(N^2/D^{\gamma})$ time when $D\le N^{\eps}$, $\eps<\eps^*$, and for $\eps<\ln4/(5\ln10)=0.1204$ this is~\cite[Theorem 25]{AV26}. We apply it to the two biadjacency matrices, with $N=n$, $D=n^{\delta}$ and the query pairs as positions.
\end{proof}

In Section~\ref{sec:exact} we extend this range to every $\delta<\epsex$ (Corollary~\ref{cor:exact}). For larger $\delta$ no algorithm faster than $O(n^{2})$ is known for natural instances.

Some conditional lower bounds use lopsided instances that do not saturate these bounds, with smaller sets or fewer queries, which merging solves in less than $n^2$ time. Lemma~\ref{lem:fewer} below derives some of them from natural instances, and the following general form covers them all.

\begin{hypothesis}[$\mathrm{LST}(r,\sigma,\kappa)$]
Let $0<\sigma\le r<2$ with $\min(r,2\sigma)\ge1/5$, and let $\kappa+\sigma\le2$. For every $\eps>0$, instances of $\LST(n,n^{r},n^{\kappa})$ in which every vertex of $A\cup B$ has at most $n^{\sigma}$ neighbours in $M$ cannot be solved in $O(n^{\kappa+\sigma-\eps})$ time.
\end{hypothesis}

Natural instances are the case $\sigma=r/2$, $\kappa=2-r/2$. The condition $\kappa+\sigma\le2$ keeps the merging time below the cost $n^{2+o(1)}$ of the whole product for small $r$. Since every set has at most $n^{\sigma}$ elements, hashing the universe into $O(n^{2\sigma})$ buckets, with $O(\log n)$ independent hash functions, preserves the answers with high probability~\cite{Pat10,GLP19}. Hence only $\min(r,2\sigma)$ matters. The restriction $\min(r,2\sigma)\ge1/5$ keeps the hypothesis clear of the range of Corollary~\ref{cor:exact}, and every use below satisfies it.

\subsection{Listing}

The dynamic bounds of~\cite{AV14} do not follow from the decision version of $\LST$. They use a capped listing problem, in which the task is to list all triangles that contain a query pair or to report that there are more than a given number of them~\cite[Theorem 10.1]{AV14}. A fast algorithm for capped listing does not obviously give a fast decision algorithm, since an instance may have many triangles, so the corresponding hypothesis has to be stated separately.

\begin{hypothesis}[$\mathrm{LSTL}(r,\sigma,\kappa,\lambda)$]
Let $r,\sigma,\kappa$ be as in $\mathrm{LST}(r,\sigma,\kappa)$ and $0\le\lambda\le\kappa+\sigma$. For every $\eps>0$, no algorithm, given an instance of $\LST(n,n^{r},n^{\kappa})$ in which every vertex of $A\cup B$ has at most $n^{\sigma}$ neighbours in $M$, lists in $O(n^{\kappa+\sigma-\eps})$ time all triangles that contain a query pair whenever there are at most $n^{\lambda}$ of them.
\end{hypothesis}

For $\lambda<\kappa$, $\mathrm{LSTL}(r,\sigma,\kappa,\lambda)$ implies $\mathrm{LST}(r,\sigma,\kappa)$, because a decision algorithm finds the query pairs that lie in triangles, and if there are at most $n^\lambda$ of them, merging their neighbourhoods lists the triangles in $O(n^{\lambda+\sigma})$ further time. For balanced graphs the listing hypothesis is the following, in the general form that matches the listing algorithm of Bj\"orklund, Pagh, Vassilevska Williams and Zwick~\cite{BPWZ14} when $\omega=2$.

\begin{hypothesis}[TLH]
For every $\eps>0$ and $m\le t\le m^{3/2}$, listing $t$ triangles of a graph with $m$ edges, or all of them if there are fewer, cannot be done in $O(m^{1-\eps}t^{1/3})$ time.
\end{hypothesis}

At $t=m$ the bound is $m^{4/3}$, and since listing $m$ triangles in a graph with $m$ edges is equivalent to All-Edges Sparse Triangle under randomized reductions, up to polylogarithmic factors~\cite{DKPW20}, TLH at $t=m$ is the balanced hypothesis BST below. The algorithms of~\cite{AV26,Maj26} count triangles without listing them, and they apply only to lopsided graphs whose middle part has fewer than $n^{\epsex}$ vertices (Theorem~\ref{thm:exact}). They do not bear on any of the listing hypotheses.

\subsection{Balanced instances}

At $\delta=1$ the three parts of a natural instance have the same size, and natural instances are All-Edges Sparse Triangle on graphs with $n$ vertices of degree about $\sqrt n$ and $m=\Theta(n^{3/2})$ edges, where merging takes $n^{2}=m^{4/3}$ time. Alman and Vassilevska Williams propose that the balanced case needs $m^{4/3-o(1)}$ time~\cite[Section 6]{AV26}. We use this hypothesis in the form for all graphs with $m$ edges.

\begin{hypothesis}[BST]
For every $\eps>0$, All-Edges Sparse Triangle on graphs with $m$ edges cannot be solved in $O(m^{4/3-\eps})$ time.
\end{hypothesis}

Several downstream reductions need more than BST, because they start from graphs of bounded degree, solve the all-nodes version, or solve many independent instances at once. We name the corresponding forms as follows, with $\eps>0$ arbitrary in each.
\begin{itemize}
\item \emph{Degree-bounded form} $\mathrm{BST}_\beta$, for $0<\beta\le1/2$: All-Edges Sparse Triangle on $n$-vertex graphs of maximum degree at most $n^{\beta}$ cannot be solved in $O(n^{1+2\beta-\eps})$ time. This is the conclusion of~\cite[Corollary 3.11]{VX20a}, and $\mathrm{BST}_{1/2}$ is the base of~\cite[Theorem 4.1]{ABKZ22}. Since such graphs have $m\le n^{3/2}$ edges, $\mathrm{BST}_{1/2}$ implies BST; the converse is not known~\cite[Section 7]{ABKZ22}.
\item \emph{All-nodes form}: All-Nodes Sparse Triangle (decide for every vertex whether it lies in a triangle) on graphs with $m$ edges cannot be solved in $O(m^{5/4-\eps})$ time. This is the statement of~\cite[Theorem 4.6]{CX24}.
\item \emph{Batched form}: $m^{2/3}$ independent instances of All-Edges Sparse Triangle with $m$ edges and $m^{2/3}$ vertices each cannot be solved in $O(m^{2-\eps})$ total time. This is what the proof of~\cite[Corollary 3.10]{VX20a} uses.
\end{itemize}


\subsection{Relations between different $\delta$}

Hardness of natural instances is not obviously monotone in $\delta$, and padding transfers it only with a loss.

\begin{lemma}[padding]\label{lem:blowup}
Let $0<\delta<\delta'<2$ and $n':=\lceil n^{(2-\delta/2)/(2-\delta'/2)}\rceil$. Every natural instance of $\LST_\delta(n)$ is a natural instance of $\LST_{\delta'}(n')$ after adding isolated vertices to all three parts. Consequently, if natural instances of $\LST_{\delta'}$ can be solved in $O(n^{2-\eps})$ time for some $\eps>(\delta'-\delta)/(2-\delta/2)$, then $\mathrm{LSTH}_\delta$ is false.
\end{lemma}

\begin{proof}
After padding, the outer parts have $n'$ vertices and the middle part $n'^{\delta'}\ge n^{\delta}$ vertices. Degrees are at most $n^{\delta/2}\le n'^{\delta'/2}$, and $Q\le n^{2-\delta/2}\le n'^{2-\delta'/2}$ by the choice of $n'$. Isolated vertices need not be written down, so an algorithm for $\LST_{\delta'}$ running in time $O(n'^{2-\eps})$ solves the original instance in time $O(n^{(2-\eps)(2-\delta/2)/(2-\delta'/2)}+n^{2-\delta/2}+n^{1+\delta/2})$, where the last two terms read the input. The first exponent is below $2$ exactly when $\eps(2-\delta/2)>\delta'-\delta$.
\end{proof}

Read in the other direction, Lemma~\ref{lem:blowup} says that $\mathrm{LSTH}_\delta$ implies the lower bound
\[
n^{\,2-\frac{\delta'-\delta}{2-\delta/2}-o(1)}
\]
for natural instances of $\LST_{\delta'}$, which approaches $n^{2}$ as $\delta'\downarrow\delta$. Instances with fewer queries inherit the hypothesis without loss.

\begin{lemma}[fewer queries]\label{lem:fewer}
Let $1/5\le2\sigma\le r<2$ and $1<\kappa\le2-\sigma$. Then $\mathrm{LSTH}_{2\sigma}$ implies $\mathrm{LST}(r,\sigma,\kappa)$.
\end{lemma}

\begin{proof}
Suppose that instances of $\LST(n,n^r,n^\kappa)$ with degrees at most $n^\sigma$ can be solved in $O(n^{\kappa+\sigma-\eps})$ time for some $\eps>0$, which we may take below $\kappa-1$. Take a natural instance of $\LST_{2\sigma}(n)$, add isolated vertices to its middle part until it has $n^r$ vertices, and split its at most $n^{2-\sigma}$ query pairs into at most $n^{2-\sigma-\kappa}+1$ groups of at most $n^{\kappa}$ pairs. With the same graph, each group is an instance of $\LST(n,n^r,n^\kappa)$ with degrees at most $n^{\sigma}$, and its input, of size $O(n^{1+\sigma}+n^\kappa)$, is within the time bound since $\kappa-\eps>1$. The natural instance is therefore solved in $O\big((n^{2-\sigma-\kappa}+1)\,n^{\kappa+\sigma-\eps}\big)=O(n^{2-\eps})$ time, since $\kappa+\sigma\le2$.
\end{proof}
\section{Which lower bounds survive}\label{sec:survive}

In this section we classify the main conditional lower bounds that were derived from 3SUM, APSP, Exact Triangle or weighted $k$-Clique. For each of them we record the shape of its hard instances and one of the following verdicts.
\begin{description}
\item[Faster.] The problem is equivalent to a refuted one and now has a polynomially faster algorithm.
\item[Refuted.] The stated lower bound is false, because a known algorithm beats it.
\item[Implied by $H$.] The bound follows from a hypothesis $H$ that no known algorithm contradicts, usually by the original derivation started from $H$ instead of the refuted hypothesis.
\item[Unaffected.] The bound rests on a hypothesis that was never derived from the refuted ones and is not refuted.
\item[Unsupported.] The base hypothesis is refuted and no surviving hypothesis is known to imply the bound. The problem need not have become easier, but the bound has lost its evidence.
\end{description}
Tables~\ref{tab:survive1} and~\ref{tab:survive2} summarize the classification, and in the rest of the section we give the reasons where they are not immediate. For a bound derived through the reductions that produce natural instances of $\LST_{2-2\gamma}$ (Section~\ref{sec:lst}), the verdict depends on the value of $\gamma$ that it uses. By Corollary~\ref{cor:exact}, these instances are easy when $2-2\gamma<\epsex$, that is, when $\gamma>1-\epsex/2=0.91078\ldots$, and otherwise $\mathrm{LSTH}_{2-2\gamma}$ implies the bounds that use them. Bounds on data structures that answer queries online can also follow from the Strong SetDisjointness Conjecture restricted to query times $N^{\tau}$ with $\tau>\tau_0:=\eps^*/(2+\eps^*)=0.0793\ldots$, which we write as $\mathrm{SSD}_{>\tau_0}$. By Corollary~\ref{cor:ssd} the conjecture fails below this range, and it survives above. For such bounds the threshold is $\eps^*$, where Majdoddin's data structure stops, and their corners with constant query or update time follow from the SetDisjointness Conjecture of P\u{a}tra\c{s}cu and Roditty~\cite[Conjecture 1]{GKLP17b}. Where the references list a full version of a paper, its theorem numbers refer to that version.

\begin{table}[p]
\centering\footnotesize
\renewcommand{\arraystretch}{1.12}
\begin{tabular}{@{}>{\raggedright}p{0.39\linewidth}>{\raggedright}p{0.17\linewidth}>{\raggedright\arraybackslash}p{0.38\linewidth}@{}}
\toprule
Lower bound & Instances & Verdict\\
\midrule
\multicolumn{3}{@{}l}{\emph{Static set problems and data structures}}\\
Offline Set Disjointness~\cite[Thm 1.4]{KPP16}, \cite[Thm 1.4]{FKP24}, \cite[Cor 3.12]{VX20a}, parameter $\gamma$ & $\LST_{2-2\gamma}$ & refuted for $\gamma>1-\epsex/2$ (Corollary~\ref{cor:exact}); implied by $\mathrm{LSTH}_{2-2\gamma}$ otherwise\\
Set Disjointness over a universe $[u]$, $m$ sets: $m^{2-o(1)}$ preprocessing or $u^{1/2-o(1)}$ query~\cite[Thm 7]{GLP19} & $\LST_r$, $u=m^r$ & refuted for $r<\eps^*$ (Proposition~\ref{prop:glp}); implied for $r>\eps^*$ (Section~\ref{sec:sets})\\
Set Disjointness trade-off at $\gamma$~\cite[Thm 1.7]{KPP16}; $p+2q\ge2$~\cite[Cor 1.8]{KPP16} & $\LST_{2-2\gamma}$, $\gamma\approx2-2/p$ & unsupported for $p>4/(2+\eps^*)=1.8413\ldots$ except at $q=0$ (Proposition~\ref{prop:kpp}); implied for smaller $p$ and at $q=0$ (Section~\ref{sec:sets})\\
Range mode, stretch-$(<2)$ distance oracles, 3SUM-Indexing over small universes~\cite[Cor 9, Thm 12, 14]{GLP19} & via~\cite[Thm 7]{GLP19} & unsupported where they use $r<\eps^*$; implied where they use $r>\eps^*$ (Section~\ref{sec:sets})\\
Set Intersection with reporting, $p+q\ge2$~\cite[Cor 5.2]{KPP16} & \cite[Thm 1.5]{KPP16} & unsupported\\
Bounds from Strong SetDisjointness~\cite[Thm 4, 8, 10, 13]{GLP19}, \cite[Thm 5, 8, 9, 13, 14]{GKLP17b} & & refuted or unsupported below query time $N^{\tau_0}$ (except the sparse case of~\cite[Thm 14]{GKLP17b}), implied by $\mathrm{SSD}_{>\tau_0}$ above (Section~\ref{sec:sets})\\
Consequences of Strong 3SUM-Indexing~\cite[Thm 1, 2, 7, 11, 12]{GKLP17b} & & unsupported since 2019~\cite{KP19,GGHPV20}; Thm 1 (Strong SetDisjointness) refuted at query times $N^{\tau}$, $\tau<\tau_0$ (Corollary~\ref{cor:ssd})\\
Set Disjointness, universe $\log^cm$, constant query time~\cite[Conj 1]{GKLP17b} & polylog universe & unaffected\\
Multiphase problem from 3SUM~\cite[Thm 3]{Pat10} & $(r,\sigma,\kappa)=(0.4,0.2,1.4)$ & implied by $\mathrm{LSTH}_{0.4}$ (Lemma~\ref{lem:fewer})\\
\midrule
\multicolumn{3}{@{}l}{\emph{Dynamic problems}}\\
Multiphase conjecture $\Rightarrow$ dynamic bounds~\cite[Thm 2]{Pat10} & & implied by the multiphase conjecture\\
st-SubConn, st-Reach, BPMatch, SC, $\emptyset$-PP from 3SUM~\cite[Thm 5.2]{AV14}; st-reachability from Exact Triangle~\cite[Cor 1.6]{VX20a}; $\alpha\in[1/6,1/3]$ & capped listing, $r=\frac{2}{3(1-\alpha)}\in[0.8,1]$ & implied by $\mathrm{LSTL}(r,\sigma,\kappa,\lambda)$ (Section~\ref{sec:dyn})\\
Decremental/incremental st-SP, BWMatch from APSP~\cite[Thm 5.4]{AV14} & one-way APSP-hard & unsupported\\
Fully dynamic MCM~\cite[Thm 1.11]{KPP16}; incremental set intersection emptiness~\cite[Thm 9]{KPP15} & $\LST_{2-2\gamma}$ & implied by OMv for every $\gamma$; the approximate variant of Thm 1.11 as Cor 1.8 (Section~\ref{sec:sets})\\
Incremental MCM, $\Omega(\hat n^{0.3903})$~\cite[Thm 1.12]{KPP16} & $\LST_{1.1231}$ & implied by $\mathrm{LSTH}_{1.1231}$\\
$d$-failure connectivity, query time $d^{1/2-o(1)}$ at deletion time $d^{a}$~\cite[Thm 5.3]{KPP16} & $\LST_\delta$, $\delta<1/a$ & implied by OMv~\cite[Cor 3.12]{HKNS15} (Section~\ref{sec:dyn})\\
Dynamic matrix inverse and relatives~\cite{BNS19}, partially dynamic distance oracles~\cite{HLS24}, dynamic attention~\cite{BSZ24} & hinted OMv & thin-hint end unsupported; main bounds implied by hinted OMv outside the refuted regime (Section~\ref{sec:dyn})\\
\bottomrule
\end{tabular}
\caption{Set problems and dynamic problems after the refutation. $\eps^*=0.17227\ldots$ (queries online), $\epsex=0.17843\ldots$ (queries known in advance); $\LST_\delta$, $\mathrm{LST}$ and $\mathrm{LSTL}$ are defined in Section~\ref{sec:lst}.}
\label{tab:survive1}
\end{table}

\begin{table}[p]
\centering\footnotesize
\renewcommand{\arraystretch}{1.12}
\begin{tabular}{@{}>{\raggedright}p{0.39\linewidth}>{\raggedright}p{0.17\linewidth}>{\raggedright\arraybackslash}p{0.38\linewidth}@{}}
\toprule
Lower bound & Instances & Verdict\\
\midrule
\multicolumn{3}{@{}l}{\emph{Triangles, cycles and distance oracles}}\\
All-Edges Sparse Triangle, $m^{4/3}$~\cite[Cor 1.1]{VX20a}, \cite[Thm 3.1, 4.3, A.3]{CX24} & $m$-edge graphs & implied by $\mathrm{BST}$ (it is $\mathrm{BST}$)\\
Reporting $m$ triangles, $m^{4/3}$~\cite[Thm 5]{Pat10} & balanced & implied by $\mathrm{BST}$ (equivalent under randomized reductions~\cite{DKPW20})\\
Enumerating $t$ triangles~\cite[Thm 1.10]{KPP16} & dense, $t\le m^{3/2}$ & implied by TLH\\
AE-Sparse Triangle, maximum degree $n^{\beta}$~\cite[Cor 3.11]{VX20a} & equal parts & implied by $\mathrm{BST}_\beta$ (it is $\mathrm{BST}_\beta$)\\
AE-Mono$\Delta$, $n^{5/2}$~\cite[Cor 3.10]{VX20a} & $\tilde O(n)$ independent instances & implied by the batched form of $\mathrm{BST}$\\
Distance oracles, dynamic APSP, cycle enumeration~\cite[Cor 1.7--1.9]{ABKZ22} & maximum degree $\sqrt n$ & implied by $\mathrm{BST}_{1/2}$\\
4-cycle and related bounds~\cite[Cor 1.11]{ABKZ22} & triangle detection, maximum degree $\sqrt n$ & unaffected (Section~\ref{sec:tri})\\
Graphs with few short cycles~\cite[Thm 1.1--1.5]{ABF23}, \cite[Thm 1.5, 1.7]{JX23} & from 3SUM & sharper exponents unsupported; weaker forms from $\mathrm{BST}_{1/2}$ through~\cite{ABKZ22}\\
Triangle detection, maximum degree $n^{1/4}$, $n^{1.5}$~\cite[Thm 1.14]{JX23} & Strong 3SUM & unsupported\\
All-Nodes Sparse Triangle, $m^{5/4}$~\cite[Thm 4.6]{CX24} & $m=N^{4/3}$ & implied by the all-nodes form (it is that form)\\
Sparse Triangle Detection, $m^{9/7}$~\cite[Thm 4.7]{CX24} & Strong Exact Triangle & implied, even with $m^{4/3}$, by the hypothesis of~\cite[Cor 1.11]{ABKZ22}\\
\midrule
\multicolumn{3}{@{}l}{\emph{Strings, geometry, convolutions}}\\
Jumbled (histogram) indexing~\cite[Thm 2, 3, 5]{ACLL14}, \cite[Thm 6, 7]{GKLP16} & (strong) Convolution-3SUM, 3SUM & unsupported\\
Local alignment, alphabet $n^{1-\delta}$~\cite[Thm 1]{AVWW14}; alphabet $\sqrt n$~\cite[Cor 1]{AVWW14} & 3SUM; Max-Weight 4-Clique & unsupported\\
Local alignment, binary alphabet~\cite[Thm 2]{AVWW14} & SETH & unaffected\\
GeomBase, 3SUM$'$~\cite{GO95} & equivalent to 3SUM & faster\\
Three collinear points, point covering, motion planning~\cite{GO95}; minimum-area triangle~\cite{King04}; polygon containment~\cite{BH01} & one-way from 3SUM & unsupported\\
Problems as hard as sorting $X+Y$, $o(n^2\log n)$ level~\cite{Bar96} & & unaffected\\
$(\min,+)$-convolution class~\cite[Thm 2]{CMWW19} & reduces to 3SUM, APSP & faster\\
MonoConvolution~\cite[Thm 7, 8]{LPV20} & equivalent to 3SUM & faster\\
\midrule
\multicolumn{3}{@{}l}{\emph{Other bases}}\\
APSP-equivalent problems~\cite{VW18,AGV15} & & faster~\cite{AV26}\\
One-way APSP-hard problems, e.g.~\cite[Thm 5.4]{AV14}, local alignment at $n^{1.5}$~\cite{AVWW14} & & unsupported\\
Average-case Zero-$k$-Clique~\cite{LLV19,AHY25} & & refuted in every form with polynomially bounded weights~\cite[Cor 39]{AV26}\\
\bottomrule
\end{tabular}
\caption{Triangle, string, geometric and other bounds after the refutation. $\mathrm{BST}_\beta$, the all-nodes and batched forms, and TLH are defined in Section~\ref{sec:lst}.}
\label{tab:survive2}
\end{table}

\subsection{Set problems and data structures}\label{sec:sets}

We begin with a published lower bound that the data structure of~\cite{AV26,Maj26} falsifies as stated. Goldstein, Lewenstein and Porat~\cite[Theorem 7]{GLP19} show from 3SUM that every data structure for Set Disjointness on $m$ sets $S_1,\dots,S_m\subseteq[u]$ of total size $N$, for every $u\in[N^{\delta},N]$ with $\delta>0$, needs $\Omega(m^{2-o(1)})$ preprocessing time or $\Omega(u^{1/2-o(1)})$ query time.

\begin{proposition}\label{prop:glp}
For every $0<r<\eps^*$ and every $q>0$ there is $c>0$ such that Set Disjointness on $m$ sets over a universe of size $u=m^{r}$ has a deterministic data structure with preprocessing time $O(m^{2-c})$ that returns the size of any intersection in $O(u^{q})$ time. In particular the conclusion of~\cite[Theorem 7]{GLP19} fails for $u=m^{r}$.
\end{proposition}

\begin{proof}
Apply the data-structure statement of~\cite[Theorem 7.4]{Maj26} to the $m\times u$ incidence matrix $X$ and to $Y=X^{\mathsf T}$, with $m$ in the role of the $N$ there and $D=u=m^{r}$. After preprocessing in $O(m^2/u^{\gamma})=O(m^{2-r\gamma})$ time, any entry of $XY$, which is the size of an intersection, is computed in $O(u^{q})$ time. Since $N\le mu$, the universe size $u=m^r$ lies in $[N^{\delta},N]$ for $\delta=r/(1+r)$ on instances with $N\ge u$, such as those of~\cite[Theorem 7]{GLP19}. Hence $q<1/2$ contradicts~\cite[Theorem 7]{GLP19}.
\end{proof}

The same data structure refutes a conjecture of Goldstein, Kopelowitz, Lewenstein and Porat that predates~\cite{AV26}.

\begin{corollary}\label{cor:ssd}
The Strong SetDisjointness Conjecture~\cite[Conjecture 3]{GKLP17b}, which asks for space $\tilde\Omega(N^2/T^2)$ at query time $T$ for sets of total size $N$, is false. It fails at every query time $T=N^{\tau}$ with $0<\tau<\tau_0=\eps^*/(2+\eps^*)$.
\end{corollary}

\begin{proof}
Goldstein, Lewenstein and Porat~\cite[Theorem 4]{GLP19} prove that the conjecture implies the following: every data structure for Set Disjointness on $m$ sets over $[u]$, for $u\in[N^{\delta},N]$, uses $\Omega(m^{2-o(1)})$ space or has $\tilde\Omega(u^{1/2-o(1)})$ query time. The data structure of Proposition~\ref{prop:glp} uses at most its preprocessing time, $O(m^{2-c})$, as space and has query time $O(u^q)$, so for $u=m^r$ with $0<r<\eps^*$ and $q<1/2$ it violates this conclusion. Hence the conjecture is false.

To see which query times are affected, we follow the proof of~\cite[Theorem 4]{GLP19}. For a parameter $u$ and a small $\eps>0$, it answers queries on arbitrary sets of total size $N$ in time $T=O(u^{1/2-\eps})$ with space $\tilde O(N^2/u^{1-\eps}+S')$, where $S'$ is the space of a data structure for at most $N/u^{1/2-\eps}$ sets over $[8u]$ with query time $O(u^{1/2-\eps})$. We use Proposition~\ref{prop:glp} for this structure, with the sets padded by empty ones to $(8u)^{1/r}$ sets, so that $S'=O(u^{(2-c)/r})$. For $u=N^{\nu}$ with $\nu=r/(1+r(\frac12-\eps))$ the padding suffices, and
\[
ST^2=\tilde O\big(N^2u^{-\eps}+N^{2-c/(1+r(1/2-\eps))}\big)=O(N^{2-\Omega(1)})
\]
at $T=N^{\tau}$ with $\tau=r(\frac12-\eps)/(1+r(\frac12-\eps))$. As $r$ ranges over $(0,\eps^*)$ and $\eps\to0$, $\tau$ takes every value in $(0,\eps^*/(2+\eps^*))$.
\end{proof}

The hard instances of~\cite[Theorem 7]{GLP19} have $m$ sets of size $O(\sqrt u)$ and $\tilde O(m^2/\sqrt u)$ queries, up to factors $u^{O(\eps)}$ for an arbitrarily small $\eps>0$. Writing $u=m^r$, they are therefore natural instances of $\LST_{r'}$ for $r'$ close to $r$. For $r>\epsex$ the bound follows from $\mathrm{LSTH}_{r'}$ for these $r'$, since a data structure with preprocessing $m^{2-\eps}$ and query time $u^{1/2-\eps}$ would solve them in $O(m^{2-\eps}+m^{2-r\eps})$ time. For $\eps^*<r<\epsex$ these instances are easy by Corollary~\ref{cor:exact}, but the bound, which concerns data structures, still follows from $\mathrm{SSD}_{>\tau_0}$ through~\cite[Theorem 4]{GLP19}, since preprocessing time bounds space. At $u=m^r$ that theorem uses the conjecture at query times about $N^{r/(2+r)}$, by the computation in the proof of Corollary~\ref{cor:ssd}, and $r/(2+r)>\tau_0$ when $r>\eps^*$. The bounds that~\cite{GLP19} derive from its Theorem 7 by further reductions behave in the same way: they are unsupported where they use it with $r<\eps^*$, and otherwise they follow from $\mathrm{SSD}_{>\tau_0}$, and for $r>\epsex$ also from $\mathrm{LSTH}_{r'}$ for $r'$ near $r$. The bounds that~\cite{GLP19,GKLP17b} derive from the Strong SetDisjointness Conjecture itself are unsupported where they use it at query times below $N^{\tau_0}$, except that on sparse graphs~\cite[Theorem 14]{GKLP17b} also follows from the Directed Reachability Hypothesis of~\cite[Conjecture 12]{GKLP17b}, through~\cite[Theorem 15]{GKLP17b}. Two of them are even refuted there:~\cite[Theorem 4]{GLP19}, by Proposition~\ref{prop:glp}, and~\cite[Theorem 5]{GKLP17b}, a bound for detecting whether an edge lies in a triangle, by the data structure of Corollary~\ref{cor:ssd} applied to the neighbourhoods of the vertices.

The trade-offs of Kopelowitz, Pettie and Porat for Set Disjointness are not refuted, because they concern data structures for all instances, but for $\gamma>1-\eps^*/2$ a data structure beats the trade-off on the instances used to prove them.

\begin{proposition}\label{prop:kpp}
For every $\gamma>1-\eps^*/2$ there is $c>0$ such that the instances of~\cite[Theorem 1.4]{KPP16} with parameter $\gamma$ admit a deterministic data structure with
\[
t_p+N^{\frac{1+\gamma}{2-\gamma}}\,t_q=O\bigl(N^{\frac{2}{2-\gamma}-c}\bigr),
\]
where $N$ is the total size of the sets, $t_p$ the preprocessing time and $t_q$ the query time. The trade-off of~\cite[Theorem 1.7]{KPP16} asserts that no data structure for Set Disjointness achieves this.
\end{proposition}

\begin{proof}
The instances have $\Theta(n\log n)$ sets of size $O(n^{1-\gamma})$ over a universe of size $D=\Theta(n^{2-2\gamma})$, so $N=\Theta(n^{2-\gamma}\log n)$, $N^{(1+\gamma)/(2-\gamma)}=\tilde\Theta(n^{1+\gamma})$ and $N^{2/(2-\gamma)}=\tilde\Theta(n^{2})$. Moreover, $D\le (n\log n)^{\eps}$ for some $\eps<\eps^*$ because $2-2\gamma<\eps^*$. Fix $q'<1/2$. By the data-structure statement of~\cite[Theorem 7.4]{Maj26} there is $\gamma'>0$ with $t_p=O(n^2/D^{\gamma'})$ and $t_q=O(D^{q'})$, so $t_p+n^{1+\gamma}t_q=\tilde O(n^{2-(2-2\gamma)\gamma'}+n^{1+\gamma+(2-2\gamma)q'})$, and both exponents are below $2$ because $q'<1/2$.
\end{proof}

Corollary~1.8 of~\cite{KPP16} ($p+2q\ge2$ for preprocessing $N^p$ and query time $N^q$) is proved by applying Theorem~1.7 with $\gamma=2-2/p+\eps'$ for a small $\eps'>0$. Since preprocessing time bounds space, and query time $N^q$ is also query time $N^{q'}$ for every $q'\ge q$, a data structure with $p+2q<2$ contradicts the Strong SetDisjointness Conjecture at query time $N^{q'}$ for $q'$ just below $1-p/2$. Hence the corollary follows from $\mathrm{SSD}_{>\tau_0}$ for $1-p/2>\tau_0$, that is, for $p<4/(2+\eps^*)=1.8413\ldots$, and for $p<4/(2+\epsex)=1.8361\ldots$ also from $\mathrm{LSTH}_{4/p-2-2\eps'}$. For $p>4/(2+\eps^*)$ Proposition~\ref{prop:kpp} beats Theorem~1.7 on its instances, and the corollary is unsupported there, with one exception. At $q=0$ it follows from the SetDisjointness Conjecture of P\u{a}tra\c{s}cu and Roditty~\cite[Conjecture 1]{GKLP17b}, which is not affected. That conjecture concerns universes of polylogarithmic size, where $N$ is quasilinear in $m$. The fully dynamic trade-off for maximum cardinality matching~\cite[Theorem 1.11]{KPP16} and the incremental one for set intersection emptiness~\cite[Theorem 9]{KPP15} survive for every $\gamma$, because the OMv conjecture, which is not affected, implies them. For Theorem~1.11, OMv rules out polynomial preprocessing together with update time $\tilde o(\sqrt m)$ for maintaining the size of a maximum matching~\cite[Corollary 3.4]{HKNS15}, and a data structure that beats the trade-off has polynomial preprocessing and update time $m^{(1-\gamma)/(2-\gamma)-\Omega(1)}$, where $(1-\gamma)/(2-\gamma)<1/2$. For~\cite[Theorem 9]{KPP15}, take the $n$ rows of the matrix of the OuMv problem~\cite[Theorem 2.7]{HKNS15}, which has $n^a$ columns, as sets, and answer each of $n$ vector pairs $(u,v)$ by inserting $v$ as a new set and asking $|u|$ emptiness queries. A data structure that beats the trade-off then solves OuMv in $O(n^{1+a}t_i+n^2t_q)=O(n^{2+a-\Omega(1)})$ time for $1-\gamma<a<2(1-\gamma)/\gamma$. The version of Theorem~1.11 for approximate matchings without augmenting paths of length $7$ is not covered by~\cite{HKNS15}. It answers Set Disjointness queries online through the matching gadget of~\cite[Section 4.2]{KPP16}, so the analysis of Corollary~1.8 applies to it, with constant update time in place of constant query time.

The reporting bound~\cite[Corollary 5.2]{KPP16} uses the instances of~\cite[Theorem 1.5]{KPP16}, which must enumerate up to $n^{2-\delta}$ elements of the intersections with $\delta\to0$. This is about as many as the merging algorithm reads. It is thus a bound on the overhead of reporting. None of the hypotheses of Section~\ref{sec:lst} covers it, and the counting algorithms of~\cite{AV26,Maj26} do not report elements.

The multiphase problem of P\u{a}tra\c{s}cu~\cite{Pat10} gives one set in its second phase, so the data structure of~\cite{AV26}, which preprocesses both families of sets, does not apply to it. The multiphase conjecture survives. Its evidence, however, came from 3SUM. The derivation~\cite[Theorem 3]{Pat10} queries the intersections of $k=R\sqrt n$ sets of size $n/R$ over a universe of size $\Theta((n/R)^2)$ with one set per vertex of the other side, for $nR$ query pairs, with $R=n^{0.75}$. In the notation of $\mathrm{LST}(r,\sigma,\kappa)$, with $n^{1.25}$ vertices on each outer side, these instances have $(r,\sigma,\kappa)=(0.4,0.2,1.4)$. A multiphase data structure that beats~\cite[Theorem 3]{Pat10} would answer all these queries in $n^{2-\Omega(1)}$ time, so $\mathrm{LST}(0.4,0.2,1.4)$ implies the theorem, and by Lemma~\ref{lem:fewer} so does $\mathrm{LSTH}_{0.4}$. In that reduction the triangles are listed only after these queries are answered, so their number affects the listing step and not the queries.

Finally, the new algorithms change what is possible for 3SUM-Indexing, where the arrays $A$ and $B$ are preprocessed and a query asks whether $a+b=z$ for some $a\in A$ and $b\in B$. A data structure with truly subquadratic preprocessing time and truly sublinear query time would have refuted the 3SUM hypothesis~\cite{DG25}, and such a data structure now exists.

\begin{proposition}\label{prop:3sumindexing}
3SUM-Indexing on $n$ integers of polynomial magnitude has a randomized data structure with preprocessing time $O(n^{2-c})$ and expected query time $O(n^{1-c})$ for some $c>0$.
\end{proposition}

\begin{proof}
Goldstein, Lewenstein and Porat~\cite[Lemma 6]{GLP19} reduce a 3SUM-Indexing instance, for any $X\in[n^{\delta},n]$ and $\eps>0$, in truly subquadratic time to $O(\eps\log X)$ instances of Set Disjointness, the $i$-th with $m_i=n\sqrt{X/u_i}$ sets of size $O(\sqrt{u_i})$ over a universe of size $u_i=X^{1+\eps}/2^{i-1}\in[X^{1-\eps},X^{1+\eps}]$, so that each 3SUM-Indexing query is answered by $O(n/\sqrt X)$ queries to each instance and truly sublinear expected additional time. Take $X=n^{1/10}$ and $\eps$ small. Then $u_i\le m_i^{0.11}$, and the data structure of~\cite[Theorem 7.4]{Maj26}, used as in Proposition~\ref{prop:glp} with $D=u_i\le m_i^{0.11}$, preprocesses the $i$-th instance in $O(m_i^2/u_i^{\gamma})\le O(n^2X^{1-(1-\eps)(1+\gamma)})$ time and answers its queries in $O(u_i^{q})\le O(X^{q(1+\eps)})$ time. For $\eps<\gamma/3$ and $q<1/4$ the preprocessing is $O(n^{2-c})$ and a 3SUM-Indexing query takes $O(n X^{q(1+\eps)-1/2}\log n)=O(n^{1-c})$ time.
\end{proof}

The 3SUM-Indexing conjecture itself, which concerns truly subquadratic space with $\tilde O(1)$ query time, is not affected~\cite[Section 1.2]{AV26}.

\subsection{Dynamic problems}\label{sec:dyn}

The 3SUM-based bounds of Abboud and Vassilevska Williams~\cite[Theorem 5.2]{AV14} use the triangle instances of~\cite[Lemma 11]{Pat10} and need their capped listing version~\cite[Theorem 10.1]{AV14}, which lists all triangles or reports that there are more than $\Delta=O(n^2/R)$. The graphs have two parts of $R\sqrt n$ vertices, a third part of $n$ vertices, degrees $O(n/R)$ into the third part and $O(nR)$ query edges, with $R\approx n^{1-3\alpha/2}$ for the trade-off parameter $\alpha\in[1/6,1/3]$. With $N:=R\sqrt n=n^{3(1-\alpha)/2}$ vertices on each outer side, they are instances of $\LST(N,N^{r},N^{\kappa})$ with degrees at most $N^{\sigma}$ and at most $N^{\lambda}$ triangles, where
\[
r=\frac{2}{3(1-\alpha)},\qquad \sigma=\frac{\alpha}{1-\alpha},\qquad \kappa=\frac{4-3\alpha}{3(1-\alpha)},\qquad \lambda=\frac{2+3\alpha}{3(1-\alpha)},
\]
so that $r\in[0.8,1]$ and $N^{\kappa+\sigma}=N^{2r}=n^2$. The parameters saturate the bounds of natural instances only at $\alpha=1/3$, and $\lambda<\kappa$ for $\alpha<1/3$. These bounds therefore follow from $\mathrm{LSTL}(r,\sigma,\kappa,\lambda)$, far from the range of the known algorithms. Pagh's problem is not derived from these instances but through the multiphase route~\cite{Pat10}. The trade-off for dynamic st-reachability stated from Exact Triangle in~\cite[Corollary 1.6]{VX20a} is the same as~\cite[Theorem 5.2]{AV14} and has the same verdict. The APSP-based bounds~\cite[Theorem 5.4]{AV14} reduce from Min-Weight Triangle with polynomial weights, which is equivalent to APSP and now faster, to the dynamic problems. Since this reduction goes only one way, these bounds are unsupported.

The bound for incremental maximum cardinality matching~\cite[Theorem 1.12]{KPP16} takes $\gamma=(1+\alpha)/(2+3\alpha)=0.43845\ldots$ with $\alpha=(\sqrt{17}-1)/8$, hence $\delta=2-2\gamma=1.1231\ldots$. From the OMv conjecture, which the refutation does not affect, Dahlgaard later derived the bound $\Omega(n^{1-o(1)})$ for incremental maximum cardinality matching, as~\cite[Section 1.6]{KPP16} notes. The bound for $d$-failure connectivity~\cite[Theorem 5.3]{KPP16} says that queries need $d^{1/2-o(1)}$ time unless preprocessing or deletions are slow. For deletion time $d^{a}$ it needs instances with $\delta=2-2\gamma<1/a$, so that the deletions are negligible, and it is supported by $\mathrm{LSTH}_\delta$ for such $\delta$ exactly when $1/a>\epsex$, that is, when $a<1/\epsex=5.604\ldots$. The data structure of Duan and Pettie discussed in~\cite[Section 5]{KPP16} has deletion time $d^{2c+4}$ with $c\ge1$, so for it the bound no longer follows from the lopsided hypotheses. It survives nevertheless, because the OMv conjecture implies the stronger bound $d^{1-o(1)}$ on the query time for every polynomial deletion time~\cite[Corollary 3.12]{HKNS15}, as~\cite[Section 5.3]{KPP16} already notes.

The hinted OMv conjectures of van den Brand, Nanongkai and Saranurak~\cite{BNS19} are refuted for thin hints, and the lower bounds that used that end of their trade-offs (for dynamic matrix inverse with fast queries, partially dynamic distance oracles~\cite{HLS24} and dynamic attention~\cite{BSZ24}) are unsupported~\cite[Section 5.4]{AV26}, although no faster algorithm for these dynamic problems follows. The main bounds of~\cite{BNS19}, at hint dimension $n^{0.53}$, use the conjectures far from the refuted range.

\subsection{Triangles, cycles and distance oracles}\label{sec:tri}

Most triangle bounds derived from Exact Triangle, 3SUM or APSP use graphs whose parts have comparable sizes, but the precise hypothesis they need varies. The bounds of Abboud, Bringmann, Khoury and Zamir for distance oracles, dynamic APSP and cycle enumeration~\cite[Corollaries 1.7--1.9]{ABKZ22} start from all-edges triangle detection in $n$-vertex graphs of maximum degree $\sqrt n$~\cite[Theorem 4.1]{ABKZ22}, which is $\mathrm{BST}_{1/2}$. The authors of~\cite{ABKZ22} do not know how to reduce the general case to it. The bound $n^{5/2}$ for AE-Mono$\Delta$~\cite[Corollary 3.10]{VX20a} packs the $m^{2/3}$ independent sparse instances, $m^{1/3}$ at a time, into instances of AE-Mono$\Delta$. It therefore needs the batched form, since a single balanced instance embedded in AE-Mono$\Delta$ gives only an $n^2$ bound. The all-nodes bound~\cite[Theorem 4.6]{CX24} uses graphs with $N$ vertices per part, $m=N^{4/3}$ edges and maximum degree $N^{1/3}$.

The refinements of Abboud, Bringmann and Fischer and of Jin and Xu for graphs with few short cycles~\cite{ABF23,JX23} assume 3SUM, so their sharper exponents are unsupported. Weaker versions, however, follow from $\mathrm{BST}_{1/2}$ through the short-cycle removal of~\cite{ABKZ22}. The bound of~\cite[Theorem 1.14]{JX23} assumes the Strong 3SUM hypothesis (integers in $[-n^2,n^2]$), which the algorithms of~\cite{AV26} refute, so it is unsupported.

The 4-cycle bounds of~\cite[Corollary 1.11]{ABKZ22} assume that detecting one triangle in a graph of maximum degree $\sqrt n$ needs $n^{2-o(1)}$ time. This hypothesis was never derived from 3SUM or APSP~\cite{ABKZ22}, and the new algorithms do not bear on it. Since an algorithm for the all-edges or the all-nodes version detects a triangle, the hypothesis implies $\mathrm{BST}_{1/2}$, hence $\mathrm{BST}$, and the all-nodes form (such graphs have $m\le n^{3/2}$ edges). The evidence offered for it in~\cite[Section 7]{ABKZ22} is a reduction (Theorem 7.6) from Zero-Triangle with parts of sizes $n$, $\sqrt n$, $\sqrt n$ and weights up to $\sqrt n$, under a Strong Zero-Triangle Conjecture stated for all parameters (Conjecture 7.5). That conjecture is refuted in its symmetric case, with parts of size $n$ and weights up to $n$, by the Exact Triangle algorithm of~\cite{AV26}, but the regime used by Theorem 7.6 is not known to be affected. The hypothesis also gives the bound $m^{4/3-o(1)}$ for detecting a triangle in graphs with $n$ vertices, maximum degree $\sqrt n$ and up to $n^{3/2}$ edges. The detection bound $m^{9/7}$ of~\cite[Theorem 4.7]{CX24} therefore survives, although it assumes the Strong Exact Triangle hypothesis (weights in $[-n,n]$), which is refuted as well.

\subsection{Strings, geometry and convolutions}

The bounds for jumbled indexing, derived from Convolution-3SUM and its strong form~\cite{ACLL14} and from 3SUM~\cite{GKLP16}, and for local alignment over large alphabets, derived from 3SUM and Max-Weight 4-Clique~\cite{AVWW14}, rest only on refuted hypotheses. The quadratic bound for binary local alignment rests on SETH~\cite[Theorem 2]{AVWW14} and is unaffected.

In computational geometry, GeomBase is equivalent to 3SUM~\cite{GO95} and now has a polynomially faster algorithm. Three collinear points, point covering and planar motion planning~\cite{GO95}, minimum-area triangle~\cite{King04} and polygon containment under translation~\cite{BH01} were shown hard by reductions from 3SUM in one direction only, so their quadratic bounds are now unsupported. Lower bounds in restricted decision-tree models remain for 3SUM itself~\cite{Eri99} and for three collinear points~\cite{ES95}. Problems shown as hard as sorting $X+Y$~\cite{Bar96}, which concern an $o(n^2\log n)$ algorithm, have a base that the new algorithms do not affect. The problems equivalent to $(\min,+)$-convolution~\cite[Theorem 2]{CMWW19} are faster, because $(\min,+)$-convolution reduces to 3SUM and to the $(\min,+)$-product~\cite{BCD14,BIS17,CMWW19}. MonoConvolution, for its part, is equivalent to 3SUM at its $n^{3/2}$ baseline~\cite[Theorems 7, 8]{LPV20}.
\section{Queries known in advance}\label{sec:exact}

The data structure behind Theorem~\ref{thm:refuted} answers the queries one at a time. When the set $W$ of query positions is known in advance, as in $\LST$ and in offline Set Disjointness, the pruned recursion of~\cite[Section 2.4.2]{AV26} visits only the leaves that the wanted entries need, and Majdoddin's count of these leaves~\cite[Lemma 6.1]{Maj26} can be used as it stands. The analysis behind Theorem~\ref{thm:refuted} instead splits the leaves at a threshold, the switching order, on the number of inner levels at which a leaf does not use the term $P_0$ that feeds only the inner product, and this split limits it to $\eps<\eps^*$. Majdoddin evaluated the range that the unsplit count allows numerically as about $0.1784$~\cite[Remark 6.2 and Section 8]{Maj26}. In this section we prove that the method reaches every $\eps$ below the constant $\epsex$ defined in~\eqref{eq:epsex}. Sections~\ref{sec:lst} and~\ref{sec:survive} use this range for the problems whose queries are known in advance.

\begin{theorem}\label{thm:exact}
For every $\eps<\epsex$ there is $\gamma>0$ such that the following holds. Let $X\in\mathbb Z^{N\times D}$ and $Y\in\mathbb Z^{D\times N}$ have entries of absolute value $N^{O(1)}$, with $2\le D\le N^{\eps}$, and let $W$ be a set of at most $N^2/\sqrt D$ positions, given together with $X$ and $Y$. Then the entries of $XY$ at $W$ can be computed deterministically in $O(N^2/D^{\gamma})$ time.
\end{theorem}

\begin{corollary}\label{cor:exact}
For every $\delta<\epsex$ and every $\mu\ge1/2$ there is $\gamma>0$ such that the counting version of $\LST(n,n^{\delta},n^{2-\mu\delta})$ can be solved deterministically in $O(n^{2-\gamma\delta})$ time. In particular $\mathrm{LSTH}_\delta$ and $\#\mathrm{LSTH}_\delta$ are false for every $\delta<\epsex$.
\end{corollary}

The corollary follows from Theorem~\ref{thm:exact} as Theorem~\ref{thm:refuted} follows from Majdoddin's theorem, with $N=n$, $D=n^\delta$ and $n^{2-\mu\delta}\le N^2/\sqrt D$.

\emph{The constant.} Let $\mathrm H(x)=-x\ln x-(1-x)\ln(1-x)$, and for $c>1$ and $0\le y\le1$ let
\[
f(y):=\mathrm H(y)+y\ln4-\tfrac12\ln2,\qquad b_c(y):=c\Big(\mathrm H\Big(\frac{1-y}{c}\Big)-\mathrm H\Big(\frac1c\Big)\Big)+y\ln4,
\]
\[
A(c):=c\ln5-\tfrac12\big(c\,\mathrm H(1/c)+(c-1)\ln4\big).
\]
Since $f'(y)=\ln\frac{4(1-y)}y>0$ on $(0,4/5)$, $f(0)<0$ and $f(4/5)>0$, $f$ has a unique root $y_f$ in $(0,4/5)$. The function $b_c$ is concave, since $b_c''(y)=-1/(1-y)-1/(c-1+y)<0$, and $b_c(0)=0$. For $y>0$ it strictly decreases in $c$, since $\partial b_c(y)/\partial c=\ln\frac{c-1}{c-1+y}<0$. We check below that $b_c(y_f)$ is positive at $c=4.8268$ and negative at $c=4.8269$, so there is a unique $c_{\min}$ with $b_{c_{\min}}(y_f)=0$, and $4.8268<c_{\min}<4.8269$. We set
\begin{equation}\label{eq:epsex}
\epsex:=\frac{\ln2}{A(c_{\min})}=0.17843\ldots.
\end{equation}
The function $A$ increases in $c$, since $A'(c)=\frac12\ln\frac{25(c-1)}{4c}>0$ for $c>25/21$.

\emph{The construction.} We recall what the proof uses from~\cite[Sections 3--6]{Maj26}, for integers $L>m\ge1$, $D=4^m$ and $N_0:=4^{L-m}$. The base identity has five terms $P_{11},P_{21},P_{12},P_{22},P_0$: the term $P_{ij}$ contributes to the outer output $z_{ij}$ and to the inner output $z_0$, and $P_0$ only to $z_0$. A \emph{squared run} tensors the identity over $2L$ levels, the last $L$ with left and right exchanged. Its outputs are strings $w$ of $2L$ output variables, and $w$ is \emph{read} if it has $z_0$ at exactly $m$ levels of each half; these $2m$ levels form the set $Q(w)$. The rows of $X$ are cut into blocks of $N_0$ rows and the columns of $Y$ into blocks of $N_0$ columns, $K_{\mathrm g}$ consecutive blocks form a \emph{row band} or a \emph{column band}, and a \emph{tile} is a row band together with a column band. With two fixed re-indexing maps and a list of $K_{\mathrm g}$ good sets of $m$ levels, the $2m+1$ squared runs of a tile compute all $K_{\mathrm g}^2$ block products of the tile, each entry as the sum of one output of each run at a read output string fixed in advance~\cite[Theorem 5.1]{Maj26}. The input arrays of a run depend only on the bands, so each band is encoded once per run. A \emph{leaf} is a string $\tau$ of $2L$ terms, its \emph{order} is $2m$ minus its number of terms $P_0$, and the product $\Pi(\tau)$ at $\tau$ is the sum over the runs of the products of the encodings at $\tau$. The entry at a read output string $w$ is the sum of $\Pi(\tau)$ over the leaves that contribute to $w$, namely those with any term at the levels of $Q(w)$ and with $P_{ij}$ at every other level at which $w$ has $z_{ij}$. For a set $U$ of read output strings, $\mathrm{Leaves}(U)$ is the set of leaves that contribute to some $w\in U$. Let $\alpha'_d:=\binom{2m}d4^d$, let $\beta_e:=\binom L{m-e}4^{L-m+e}$ be the number of strings of $L$ terms with exactly $m-e$ terms $P_0$, and let $\beta'_d:=\sum_{d_1+d_2=d}\beta_{d_1}\beta_{d_2}$ with $0\le d_1,d_2\le m$. Exactly $\alpha'_d$ leaves of order $d$ contribute to each read output string, exactly $\beta'_d$ leaves of order $d$ have at most $m$ terms $P_0$ in each half, and every leaf that contributes to a read output string has at most $m$ in each half. Hence~\cite[Lemma 6.1]{Maj26}
\begin{equation}\label{eq:leaves}\tag{$\ast$}
|\mathrm{Leaves}(U)|\le\sum_{d=0}^{2m}\min\{|U|\alpha'_d,\beta'_d\}.
\end{equation}

\begin{proof}[Proof of Theorem~\ref{thm:exact}]
Let $\eps<\epsex$. Since $A$ is continuous and increasing, there is $c\in(c_{\min},4.8269)$ with $A(c)<\ln2/\eps$. Then $b_c(y_f)<b_{c_{\min}}(y_f)=0$, so there is $y'<y_f$ with $b_c(y')<0$, and $f(y')<0$. Since $f$ increases on $[0,4/5]$, $f\le f(y')$ on $[0,y']$; since $b_c$ is concave with $b_c(0)=0$, $b_c(y)\le\frac y{y'}b_c(y')\le b_c(y')$ on $[y',1]$. Hence
\begin{equation}\label{eq:gap}
\max_{0\le y\le1}\min\{f(y),b_c(y)\}\le-g,\qquad g:=-\max\{f(y'),b_c(y')\}>0 .
\end{equation}
Choose $\gamma>0$ with $\gamma<g/(2\ln2)$ and $A(c)+\gamma\ln2<\ln2/\eps$.

We use this construction. We pad $D$ to $4^m$ with $4^{m-1}<D\le4^m$, so that $|W|\le2^{1-m}N^2$ and $N\ge4^{(m-1)/\eps}$, and from now on write $D=4^m$. Let $L:=\lceil cm\rceil$, so that $c':=L/m\in[c,c+1/m)$, and let $K=\binom Lm$, so that $\beta_0=KN_0$. The list of good sets has $K_{\mathrm g}\ge\mu_\infty^2K$ entries, where $\mu_\infty^2=0.0833\ldots$~\cite[Lemma 4.1]{Maj26}, so a tile has $E:=K_{\mathrm g}^2N_0^2$ entries.

\emph{The algorithm.} It computes the encodings of all row and column bands, $2m+1$ arrays of $O(25^L)$ numbers per band~\cite[Section 5]{Maj26}. Then, for every tile $T$ in the set $\mathcal T$ of tiles, it runs the pruned recursion~\cite[Section 2.4.2]{AV26} on the $2L$ levels, with the set $W_T$ of the output strings of the positions of $W$ that lie in $T$ and with the product $\Pi(\tau)$ returned at a leaf $\tau$~\cite[Section 6]{Maj26}. By~\cite[Theorem 5.1]{Maj26} and~\cite[Lemma 10]{AV26}, this computes the wanted entries, visits exactly the leaves in $\mathrm{Leaves}(W_T)$, and uses $O(L^2)$ operations per visited leaf. There are at most $4N/(K_{\mathrm g}N_0)$ bands and $|\mathcal T|\le4N^2/E$. The re-indexing maps~\cite[Lemma 4.1]{Maj26}, the lists of good sets and the location of the output strings take $O(NL^{O(1)}+LN^2/N_0^2+L^2|W|)$ operations, as in the proof of~\cite[Theorem 7.2]{Maj26}. All numbers have $O(\log N)$ bits by the argument of~\cite[Section 7]{Maj26}, since $L\le(c+1)m$ and $N\ge D^{1/\eps}$.

\emph{Leaves.} We sum~\eqref{eq:leaves} with $U=W_T$ over the tiles. Since $\sum_{T\in\mathcal T}\min\{x_T,y\}\le\min\{\sum_Tx_T,|\mathcal T|\,y\}$, $|W|\le2^{1-m}N^2$ and $E\ge\mu_\infty^4K^2N_0^2=\mu_\infty^4\beta_0^2$, we obtain
\[
\sum_{T\in\mathcal T}|\mathrm{Leaves}(W_T)|\le\sum_{d=0}^{2m}\min\Big\{|W|\alpha'_d,\frac{4N^2}{E}\beta'_d\Big\}\le4N^2\sum_{d=0}^{2m}\min\Big\{\frac{\alpha'_d}{2^m},\frac{\beta'_d}{\mu_\infty^4\beta_0^2}\Big\}.
\]
Write $y=d/(2m)\in[0,1]$. The bounds $e^{n\mathrm H(k/n)}/(n+1)\le\binom nk\le e^{n\mathrm H(k/n)}$ give $\alpha'_d/2^m\le e^{2mf(y)}$ and $\beta_e/\beta_0\le(L+1)e^{mb_{c'}(e/m)}$. By concavity, $b_{c'}(z_1)+b_{c'}(z_2)\le2b_{c'}(y)$ whenever $z_1+z_2=2y$, so $\beta'_d/\beta_0^2\le(m+1)(L+1)^2e^{2mb_{c'}(y)}$, and $b_{c'}\le b_c$ because $c'\ge c$. With~\eqref{eq:gap},
\[
\sum_{T\in\mathcal T}|\mathrm{Leaves}(W_T)|\le4\mu_\infty^{-4}(2m+1)(m+1)(L+1)^2\,N^2e^{-2mg},
\]
so the pruned recursions use $O(L^2m^4N^2e^{-2mg})=O(N^2D^{-g/\ln2}\log^6D)$ operations, as $e^{2m}=D^{1/\ln 2}$.

\emph{Encodings and tiles.} The encodings take $O(m\,25^L N/(K_{\mathrm g}N_0))$ operations, which is $O(N^2/D^\gamma)$ when $mD^\gamma25^L/(K_{\mathrm g}N_0)\le N$. This condition also gives the condition $N\ge KN_0$ of the tiling, since $25^L\ge K^2N_0^2$~\cite[proof of Corollary 7.3]{Maj26}. As there, $K\ge e^{L\mathrm H(m/L)}/(L+1)$, and $L\ln\frac{25}4-L\mathrm H(m/L)$ increases in $L$ with derivative at most $\ln\frac{25}4$, so that
\[
\frac{mD^\gamma\,25^L}{K_{\mathrm g}N_0}\le\frac{25\,m(L+1)}{4\mu_\infty^2}\,e^{2m(A(c)+\gamma\ln2)} .
\]
Since $A(c)+\gamma\ln2<\ln2/\eps$ and $N\ge4^{(m-1)/\eps}=e^{2(m-1)\ln2/\eps}$, the condition holds once $m$ exceeds a constant depending on $\eps$; for smaller $m$, $D$ is bounded and the statement is trivial. The total time is $O(N^2/D^\gamma)$.
\end{proof}

\emph{The numerical value.} Let $y_0:=1379/20000$, $y_1:=6897/100000$, $\eps_0:=100000/560443=0.178430\ldots$ and $\eps_1:=5000/28021=0.178437\ldots$. We check that
\begin{equation}\label{eq:cert}
\begin{gathered}
f(y_0)<0,\qquad b_{4.8269}(y_0)<0,\qquad A(4.8269)<\frac{\ln2}{\eps_0},\\
f(y_1)>0,\qquad b_{4.8268}(y_1)>0,\qquad A(4.8268)>\frac{\ln2}{\eps_1}.
\end{gathered}
\end{equation}
Each of these says that a combination of logarithms of rational numbers with rational coefficients has a given sign. Multiplied by a common denominator of the coefficients ($20000$, $20000$, $100000$, $100000$, $100000$ and $5000$) and exponentiated, they become the inequalities
\begin{gather*}
20000^{20000}<2^{7242}\cdot1379^{1379}\cdot18621^{18621},\\
2^{2758}\cdot10000^{20000}\cdot38269^{76538}\cdot96538^{96538}<18621^{18621}\cdot48269^{96538}\cdot77917^{77917},\\
5^{482690}\cdot10000^{50000}\cdot38269^{191345}<2^{943133}\cdot48269^{241345},\\
2^{36206}\cdot6897^{6897}\cdot93103^{93103}<100000^{100000},\\
12067^{482680}\cdot93103^{93103}\cdot389577^{389577}<2^{13794}\cdot2500^{100000}\cdot9567^{382680}\cdot482680^{482680},\\
2^{47155}\cdot12067^{12067}<5^{24134}\cdot2500^{2500}\cdot9567^{9567},
\end{gather*}
which we verify in exact integer arithmetic (computed$^\dagger$; see Appendix~\ref{sec:comp}). The first two give $y_0<y_f$ and, by concavity, $b_{4.8269}(y_f)<0$, so $c_{\min}<4.8269$, and with the third, $\epsex>\eps_0>0.17843$. The fourth and fifth give $y_f<y_1$ and $b_{4.8268}(y_f)>0$, since $b_{4.8268}$ is concave and positive at $y_1$, so $c_{\min}>4.8268$, and with the sixth, $\epsex<\eps_1<0.17844$. Unlike the split form of~\cite[Corollary 7.3]{Maj26}, which needs $c>5$, the exact count works for these $c<5$.
\section{Why the analysis stops at $\ln4/(5\ln5)$}\label{sec:evidence}

The hypotheses of Section~\ref{sec:lst} are stated beyond the range of the known algorithms, and it is fair to ask whether a better base identity would move that range. In this section we collect what is known about this question. Most of it is due to Majdoddin~\cite[Appendix A]{Maj26}. We add the enumeration of the shapes that could improve the closed-form range and Koszul-flattening bounds for identities with two inner outputs. In short, no base identity in the classes analysed here is known to beat $\eps^*$: among border identities with one private term, $kn+1$ terms and at most one shared variable, only the shape of the five-term tensor attains it (Proposition~\ref{prop:shapes}); with several private terms, when every outer output lies in a term that covers no other outer output, the shapes with $k=1$, $(k,n)=(2,2)$ and $(k,n)=(2,3)$ give no saving or do not exist, and larger shapes are open; and the two natural profiles with two disjoint inner outputs do not exist (Proposition~\ref{prop:multi}).

A \emph{base identity} is a decomposition $\sum_{\lambda=1}^{R}\varphi_\lambda\psi_\lambda\chi_\lambda$, exact up to an error that the method tolerates or in the border sense, of the trilinear form $\sum_{i\le k,\,j\le n}x_iy_jz_{ij}+F\,z_0$, where $F$ is a bilinear form whose rank $q_0$ is the \emph{inner length}. The method takes the $L$-th tensor power, keeps the output strings that contain $z_0$ at exactly $m=L/c$ positions, and computes only the leaf products that the wanted outputs need~\cite[Section 2]{AV26}. A term is \emph{private} if its output form is a multiple of $z_0$. A variable of $F$ that also occurs in the outer product is \emph{shared}. For one shared variable, $S(k,n,q')$ denotes the tensor with inner form $\sum_{s\le q'}p_sq_s+cy_1$, of effective inner length $q'+1$~\cite[Appendix A.5]{Maj26}. The five-term partial-product tensor of~\cite{Cop82,Maj26} is $S(2,2,1)$.

\paragraph{The closed-form range.} The analysis of~\cite{Maj26} saves a polynomial factor exactly for $\eps<\eps^*_5=\ln4/(5\ln5)$ with the five-term tensor. That of~\cite{AV26} does so exactly for $\eps<\eps^*_{10}=\ln4/(5\ln10)=0.1204$ with Schönhage's ten-term identity. Both limits have the form
\begin{equation}\label{eq:range}
\eps^*_R=\frac{2\ln q_0}{R\ln R}
\end{equation}
for an identity with $R$ terms and inner length $q_0$ per half of the squared run ($R=5$, $q_0=2$ and $R=10$, $q_0=4$). The reason is that in both cases the leaf count needs $c>R$, and at $c=R$ the condition that a tile fits coincides with the cost of the encodings~\cite[Proposition 8.1]{Maj26}. The derivation uses only these features, so we use~\eqref{eq:range} to compare identities with one private term in which every outer output lies in exactly one term. This limits the closed-form analysis, not the method: with $W$ known in advance the method reaches every $\eps<\epsex$ with the five-term tensor (Theorem~\ref{thm:exact}), and numerically about $0.1292$ with Schönhage's identity~\cite[Section 8]{Maj26}.

\paragraph{Barriers.} Majdoddin proves the following barriers.
\begin{itemize}
\item For $k,n\ge2$, an exact identity whose inner variables are disjoint from the outer ones, with a harmless error, has $q_0\le R-k-n$~\cite[Proposition A.2]{Maj26}.
\item A border identity has $q_0\le R-k-n+1$ with disjoint inner variables and effective inner length at most $R-k-n+2$ with one shared variable~\cite[Propositions A.4, A.5]{Maj26}.
\item A run in which every output is a correct single output of a distinct entry and block cannot use two shared variables on the same side, nor, if the blocks that compute each entry are disjoint, one on each side~\cite[Theorem A.9]{Maj26}.
\item $R_0$ private terms give a saving only if $R_0^2R_1^{2(c-1)}<q_0$, where every outer output lies in at least $R_1$ terms that cover no other outer output~\cite[Lemma A.1]{Maj26}.
\end{itemize}
\noindent The exact identity obtained from Schönhage's by $z_{11}\mapsto z_{11}+z_0$ reaches inner length $R-k-n+1$ but shares $x_1$ and $y_1$, which Theorem~A.9 rules out~\cite[Appendix A.1]{Maj26}. Full products as base identities are excluded for many shapes~\cite[Theorem A.14, Corollary A.18]{Maj26}.

\paragraph{One private term.} Combining the cap with~\eqref{eq:range} leaves only a few shapes.

\begin{proposition}\label{prop:shapes}
Let a border identity (for instance an exact identity without error) have one private term, outer product $\langle k,1,n\rangle$ with $k\le n$, $R=kn+1$ terms, at most one shared variable and inner length $q_0$. If $\eps^*_R\ge\eps^*$, then $(k,n,q_0)$ is $(2,2,2)$, the shape of the five-term tensor, for which $\eps^*_R=\eps^*$, or one of $(1,1,2)$, $(1,2,2)$, $(1,3,2)$, $(1,4,2)$, $(2,2,3)$, $(2,3,4)$. No identity of the last six shapes exists.
\end{proposition}

\begin{proof}
Since $q_0<R$, $\eps^*_R<2/R\le1/6<\eps^*$ for $R\ge12$ (as $5^5=3125<4096=4^6$), so $kn\le10$. Evaluating~\eqref{eq:range} for these shapes with $q_0\le R-k-n+2$ gives the list, with equality $\eps^*_R=2\ln2/(5\ln5)=\eps^*$ for $(1,4,2)$ and $(2,2,2)$ (computed$^\dagger$). Each of the last six shapes has $q_0=R-k-n+2$, so it needs one shared variable, and up to exchanging left and right its tensor is $S(k,n,q_0-1)$ or $S(n,k,q_0-1)$. For $(1,n,2)$, $S(n,1,1)$ is concise of left dimension $n+2>R$, and $S(1,n,1)$ has border rank at least $n+2$ for $n\le6$~\cite[Remark A.6]{Maj26}. For $(2,2,3)$ and $(2,3,4)$, $S(2,2,2)$, $S(2,3,3)$ and $S(3,2,3)$ have border rank at least $6$, $8$ and $8$~\cite[Remark A.7]{Maj26}, more than $R=5$ and $R=7$. Table~\ref{tab:koszul} reproduces these bounds. Identities that are exact only up to a tolerated error are covered by~\cite[Proposition A.2]{Maj26} when $k,n\ge2$ and their inner variables are disjoint from the outer ones, and not otherwise.
\end{proof}

With $R_0\ge2$ private terms,~\eqref{eq:range} is not the range of the method. Adding $R_0-1$ private terms $p_sq_sz_0$ to the five-term tensor gives border identities with $R=R_0+4$ terms and $q_0=R_0+1$, for which~\eqref{eq:range} exceeds $\eps^*$ when $R_0\le5$. By~\cite[Lemma A.1]{Maj26}, however, they give no saving at all, since $R_0^2\ge q_0$. In general, when every outer output lies in a term that covers no other outer output, Lemma A.1 requires $R_0^2<q_0\le R-k-n+2=(k-1)(n-1)+R_0+1$. For $k=1$ and for $(k,n)=(2,2)$ this is impossible, and for $(k,n)=(2,3)$ it forces $R_0=2$ and $q_0=5$. No border identity attains this, because $S(2,3,4)$ and $S(3,2,4)$ have border rank at least $9>8$ (Table~\ref{tab:koszul}). For larger shapes with $R_0\ge2$ we do not know the range.

\paragraph{Several inner outputs.} The barriers of~\cite{Maj26} assume one inner output per level. A natural way around them is to let the outer terms serve two inner products at once. The private-leaf count suggests that this would help. For a profile of terms, the leaf model of~\cite{Maj26} gives a rate value~\cite[Remark 6.2 and Appendix A.1]{Maj26}: the largest product $\eps\gamma$ of range and saving that the exact count of leaves allows, maximised numerically over the parameters of the construction. With pruned encodings the five-term tensor scores $\eps\gamma=0.0061$ in this model, at $c=L/m\approx10.85$ with $\eps\approx0.0811$ and $\gamma\approx0.0756$ (against $0.005825$ in~\cite{Maj26}). The profile with outer product $\langle2,1,2\rangle$, two private terms and four outer terms that each serve two inner outputs of length $2$ scores $0.0102$, at $c\approx6.37$ with $\eps\approx0.1258$ and $\gamma\approx0.0814$, and the analogous profile with outer product $\langle3,1,3\rangle$ and two inner outputs of length $4$ scores $0.0074$, at $c\approx11.51$ with $\eps\approx0.1013$ and $\gamma\approx0.0729$ (computed$^\dagger$). Proposition~\ref{prop:multi} shows that neither profile exists when the inner products are disjoint.

\begin{proposition}\label{prop:multi}
The tensor $\langle2,1,2\rangle\oplus\langle1,2,1\rangle\oplus\langle1,2,1\rangle$ has border rank at least $7$, and $\langle3,1,3\rangle\oplus\langle1,4,1\rangle\oplus\langle1,4,1\rangle$ has border rank at least $13$, while the two profiles need $6$ and $11$ terms.
\end{proposition}

\begin{proof}
The bounds come from Koszul flattenings~\cite{LO13}, and the ranks are listed in Table~\ref{tab:koszul}.
\end{proof}

\begin{table}[!htb]
\centering\small
\begin{tabular}{@{}lcccc@{}}
\toprule
Tensor & flattening & rank & bound & terms\\
\midrule
$S(1,n,1)$, $n=1,2,3,4$ & $B$ ($n=1$), $A$; $p=1$ & $3,7,9,11$ & $3,\ 3.5,\ 4.5,\ 5.5$ & $n+1$\\
$S(2,2,2)$ & $C$, $p=1$ & $22$ & $5.5$ & $5$\\
$S(2,3,3)$ & $C$, $p=3$ & $141$ & $7.05$ & $7$\\
$S(3,2,3)$ & $C$, $p=1$ & $45$ & $7.5$ & $7$\\
$S(2,3,4)$; $S(3,2,4)$ & $C$, $p=3$; $p=1$ & $161$; $51$ & $8.05$; $8.5$ & $8$\\
$\langle2,1,2\rangle\oplus\langle1,2,1\rangle^{\oplus2}$ & $C$, $p=2$ & $66$ & $6.6$ & $6$\\
$\langle3,1,3\rangle\oplus\langle1,4,1\rangle^{\oplus2}$ & $C$, $p=5$ & $3102$ & $12.31$ & $11$\\
\bottomrule
\end{tabular}
\caption{Koszul-flattening lower bounds on border rank. The flattening is $\Lambda^pV\otimes U^*\to\Lambda^{p+1}V\otimes W$ for a factor $V$ ($C$: the output factor) and the bound is the rank divided by $\binom{\dim V-1}{p}$; ``terms'' is the number of terms the identity or profile would have. Ranks are exact over $\mathbb Q$ and agree with ranks modulo $2^{31}-1$.$^\dagger$}
\label{tab:koszul}
\end{table}
\section{Open problems}\label{sec:open}

We close with some questions that the classification leaves open.

\begin{enumerate}
\item Is $\mathrm{LSTH}_\delta$ true for some $\delta$? Is hardness monotone in $\delta$, so that there is a threshold $\delta^*\in[\epsex,1]$ below which natural instances are easy and above which they are hard? Lemma~\ref{lem:blowup} gives only a weak form of monotonicity. Theorem~\ref{thm:exact} needs the queries in advance. Can a data structure that answers queries online reach beyond $\eps^*$?
\item Is there a base identity outside the classes of Section~\ref{sec:evidence} whose closed-form range, with queries online, exceeds Coppersmith's exponent? The thin full products that~\cite[Appendix A.9]{Maj26} does not exclude, the smallest being $\langle34,2,35\rangle$, are candidates, and so are identities with several private terms, whose range is not known.
\item Can capped listing, triangle listing or Set Intersection with reporting be solved faster on lopsided instances, as counting can? A positive answer would bear on the listing hypotheses and on the status of~\cite[Corollary 5.2]{KPP16}.
\item Does $\mathrm{LST}(r,\sigma,\kappa)$ follow from the natural hypotheses also when $2\sigma>r$ or $\kappa\le1$, the cases that Lemma~\ref{lem:fewer} leaves out? Does the listing hypothesis $\mathrm{LSTL}(r,\sigma,\kappa,\lambda)$ follow from them, or from $\mathrm{BST}$? Does $\mathrm{BST}$ imply $\mathrm{BST}_{1/2}$~\cite{ABKZ22}?
\item Can the quadratic lower bounds for three collinear points and the other 3SUM-hard problems of computational geometry be derived from a surviving hypothesis, such as $k$-SUM for some $k\ge4$, $\mathrm{BST}$, or SETH? No polylogarithmic improvement is known for three collinear points~\cite{AV26}.
\item Triangle detection in tripartite graphs with parts of sizes $n$, $n$ and $\sqrt n$ and $O(n^{3/2})$ edges would have consequences for girth approximation if it could be solved in $O(n^{2-\eps})$ time~\cite{RV12,AV26}. These instances lie outside the range of Theorems~\ref{thm:refuted} and~\ref{thm:exact}. Can they be solved faster?
\end{enumerate}

\appendix
\section{Computations}\label{sec:comp}

The values marked $\dagger$ were computed with short Python programs. The ranks in Table~\ref{tab:koszul}, the inequalities~\eqref{eq:cert} and the comparisons in the proof of Proposition~\ref{prop:shapes} are exact: the ranks by elimination over $\mathbb Q$, with a cross-check modulo $2^{31}-1$, and the inequalities and comparisons as inequalities between integers. For each shape of Proposition~\ref{prop:shapes} with $q_0\ge2$, a rational number $t=a/b$ lies strictly between $\log_2q_0$ and $\frac R5\log_5R$, or equals both when they coincide, so the comparison amounts to comparing $q_0^b$ with $2^a$ and $5^{5a}$ with $R^{Rb}$. The other ranges and the leaf-model scores are floating-point evaluations. Lean~4 also proves the integer forms of these inequalities and comparisons, and lower bounds on the ranks equal to the values in Table~\ref{tab:koszul}, from which the border-rank bounds follow with the Landsberg--Ottaviani inequality as an explicit hypothesis; the passage from the integer forms back to logarithms is not formalized. The programs, their outputs and the Lean files are in the supplement to this paper, \url{https://doi.org/10.5281/zenodo.23602530}.

\begin{thebibliography}{GGHPV20}\small
\bibitem[ABF23]{ABF23} A.~Abboud, K.~Bringmann, and N.~Fischer. Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics. In \emph{STOC 2023}, pages 391--404. Full version: arXiv:2211.07058.
\bibitem[ABKZ22]{ABKZ22} A.~Abboud, K.~Bringmann, S.~Khoury, and O.~Zamir. Hardness of approximation in P via short cycle removal: cycle detection, distance oracles, and beyond. In \emph{STOC 2022}, pages 1487--1500. Full version: arXiv:2204.10465.
\bibitem[ACLL14]{ACLL14} A.~Amir, T.~M. Chan, M.~Lewenstein, and N.~Lewenstein. On hardness of jumbled indexing. In \emph{ICALP 2014}, LNCS 8572, pages 114--125. Full version: arXiv:1405.0189.
\bibitem[AGV15]{AGV15} A.~Abboud, F.~Grandoni, and V.~Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In \emph{SODA 2015}, pages 1681--1697.
\bibitem[AHY25]{AHY25} J.~Alman, Y.~Huang, and K.~Yeo. Fine-grained complexity in a world without cryptography. In \emph{EUROCRYPT 2025, Part VII}, LNCS 15607, pages 375--405.
\bibitem[AV14]{AV14} A.~Abboud and V.~Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In \emph{FOCS 2014}, pages 434--443. Full version: arXiv:1402.0054.
\bibitem[AV26]{AV26} J.~Alman and V.~Vassilevska Williams. Truly subquadratic 3SUM and truly subcubic APSP via triangles in sparse lopsided graphs. arXiv:2610.06783, 2026.
\bibitem[AVW14]{AVWW14} A.~Abboud, V.~Vassilevska Williams, and O.~Weimann. Consequences of faster alignment of sequences. In \emph{ICALP 2014}, LNCS 8572, pages 39--51.
\bibitem[Bar96]{Bar96} A.~Hern\'andez Barrera. Finding an $o(n^2\log n)$ algorithm is sometimes hard. In \emph{CCCG 1996}, pages 289--294.
\bibitem[BCD{+}14]{BCD14} D.~Bremner, T.~M. Chan, E.~D. Demaine, J.~Erickson, F.~Hurtado, J.~Iacono, S.~Langerman, M.~P\u{a}tra\c{s}cu, and P.~Taslakian. Necklaces, convolutions, and $X+Y$. \emph{Algorithmica} 69(2):294--314, 2014.
\bibitem[BHP01]{BH01} G.~Barequet and S.~Har-Peled. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard. \emph{Int.\ J.\ Comput.\ Geom.\ Appl.}\ 11(4):465--474, 2001.
\bibitem[BIS17]{BIS17} A.~Backurs, P.~Indyk, and L.~Schmidt. Better approximations for tree sparsity in nearly-linear time. In \emph{SODA 2017}, pages 2215--2229.
\bibitem[BNS19]{BNS19} J.~van den Brand, D.~Nanongkai, and T.~Saranurak. Dynamic matrix inverse: improved algorithms and matching conditional lower bounds. In \emph{FOCS 2019}, pages 456--480. Full version: arXiv:1905.05067.
\bibitem[BPWZ14]{BPWZ14} A.~Bj\"orklund, R.~Pagh, V.~Vassilevska Williams, and U.~Zwick. Listing triangles. In \emph{ICALP 2014}, LNCS 8572, pages 223--234.
\bibitem[BSZ24]{BSZ24} J.~van den Brand, Z.~Song, and T.~Zhou. Algorithm and hardness for dynamic attention maintenance in large language models. In \emph{ICML 2024}, PMLR 235, pages 49008--49028.
\bibitem[CMWW19]{CMWW19} M.~Cygan, M.~Mucha, K.~W\k{e}grzycki, and M.~W\l{}odarczyk. On problems equivalent to $(\min,+)$-convolution. \emph{ACM Trans.\ Algorithms} 15(1):14:1--14:25, 2019. Full version: arXiv:1702.07669.
\bibitem[Cop82]{Cop82} D.~Coppersmith. Rapid multiplication of rectangular matrices. \emph{SIAM J.\ Comput.}\ 11(3):467--471, 1982.
\bibitem[CVX22]{CVX22} T.~M. Chan, V.~Vassilevska Williams, and Y.~Xu. Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. In \emph{STOC 2022}, pages 1501--1514.
\bibitem[CX24]{CX24} T.~M. Chan and Y.~Xu. Simpler reductions from exact triangle. In \emph{SOSA 2024}, pages 28--38. Full version: arXiv:2310.11575.
\bibitem[DG25]{DG25} I.~Dinur and A.~Golovnev. Improved time-space tradeoffs for 3SUM-Indexing. arXiv:2512.04258, 2025.
\bibitem[DKPW20]{DKPW20} L.~Duraj, K.~Kleiner, A.~Polak, and V.~Vassilevska Williams. Equivalences between triangle and range query problems. In \emph{SODA 2020}, pages 30--47.
\bibitem[Eri99]{Eri99} J.~Erickson. Lower bounds for linear satisfiability problems. \emph{Chicago J.\ Theoret.\ Comput.\ Sci.}\ 1999(8).
\bibitem[ES95]{ES95} J.~Erickson and R.~Seidel. Better lower bounds on detecting affine and spherical degeneracies. \emph{Discrete Comput.\ Geom.}\ 13:41--57, 1995.
\bibitem[FKP24]{FKP24} N.~Fischer, P.~Kaliciak, and A.~Polak. Deterministic 3SUM-hardness. In \emph{ITCS 2024}, LIPIcs 287, 49:1--49:24. Full version: arXiv:2310.12913.
\bibitem[FPS26]{FPS26} N.~Fischer, A.~Polak, and J.~Schmidt. 3SUM is really hard: a real-to-integer reduction. In \emph{FOCS 2026}. arXiv:2610.10153.
\bibitem[GGHPV20]{GGHPV20} A.~Golovnev, S.~Guo, T.~Horel, S.~Park, and V.~Vaikuntanathan. Data structures meet cryptography: 3SUM with preprocessing. In \emph{STOC 2020}, pages 294--307.
\bibitem[GKLP16]{GKLP16} I.~Goldstein, T.~Kopelowitz, M.~Lewenstein, and E.~Porat. How hard is it to find (honest) witnesses? In \emph{ESA 2016}, LIPIcs 57, 45:1--45:16. Full version: arXiv:1706.05815.
\bibitem[GKLP17]{GKLP17b} I.~Goldstein, T.~Kopelowitz, M.~Lewenstein, and E.~Porat. Conditional lower bounds for space/time tradeoffs. In \emph{WADS 2017}, LNCS 10389, pages 421--436. Full version: arXiv:1706.05847.
\bibitem[GLP19]{GLP19} I.~Goldstein, M.~Lewenstein, and E.~Porat. On the hardness of set disjointness and set intersection with bounded universe. In \emph{ISAAC 2019}, LIPIcs 149, 7:1--7:22. Full version: arXiv:1910.00831.
\bibitem[GO95]{GO95} A.~Gajentaan and M.~H. Overmars. On a class of $O(n^2)$ problems in computational geometry. \emph{Comput.\ Geom.}\ 5(3):165--185, 1995.
\bibitem[HKNS15]{HKNS15} M.~Henzinger, S.~Krinninger, D.~Nanongkai, and T.~Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In \emph{STOC 2015}, pages 21--30.
\bibitem[HLS24]{HLS24} B.~Haeupler, Y.~Long, and T.~Saranurak. Dynamic deterministic constant-approximate distance oracles with $n^{\epsilon}$ worst-case update time. In \emph{FOCS 2024}, pages 2033--2044.
\bibitem[JX23]{JX23} C.~Jin and Y.~Xu. Removing additive structure in 3SUM-based reductions. In \emph{STOC 2023}, pages 405--418. Full version: arXiv:2211.07048.
\bibitem[Kin04]{King04} J.~King. A survey of 3SUM-hard problems. Manuscript, 2004.
\bibitem[KL26]{KL26} S.~R. Karingula and S.~Lovett. A simplified proof of polynomial improvements for 3SUM and APSP. arXiv:2610.15663, 2026.
\bibitem[KP19]{KP19} T.~Kopelowitz and E.~Porat. The strong 3SUM-INDEXING conjecture is false. arXiv:1907.11206, 2019.
\bibitem[KPP15]{KPP15} T.~Kopelowitz, S.~Pettie, and E.~Porat. Dynamic set intersection. In \emph{WADS 2015}, LNCS 9214, pages 470--481. Full version: arXiv:1407.6755.
\bibitem[KPP16]{KPP16} T.~Kopelowitz, S.~Pettie, and E.~Porat. Higher lower bounds from the 3SUM conjecture. In \emph{SODA 2016}, pages 1272--1287. Full version: arXiv:1407.6756v3.
\bibitem[KPS17]{KPS17} M.~K\"unnemann, R.~Paturi, and S.~Schneider. On the fine-grained complexity of one-dimensional dynamic programming. In \emph{ICALP 2017}, LIPIcs 80, 21:1--21:15.
\bibitem[LLV19]{LLV19} R.~LaVigne, A.~Lincoln, and V.~Vassilevska Williams. Public-key cryptography in the fine-grained setting. In \emph{CRYPTO 2019, Part III}, LNCS 11694, pages 605--635.
\bibitem[LO13]{LO13} J.~M. Landsberg and G.~Ottaviani. Equations for secant varieties of Veronese and other varieties. \emph{Ann.\ Mat.\ Pura Appl.}\ 192(4):569--606, 2013.
\bibitem[LPV20]{LPV20} A.~Lincoln, A.~Polak, and V.~Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions. In \emph{ITCS 2020}, LIPIcs 151, 53:1--53:18. Full version: arXiv:2009.14479.
\bibitem[Maj26]{Maj26} R.~Majdoddin. Thin matrix products up to $D\le N^{0.172}$ and lossless reductions for 3SUM, Exact Triangle and APSP, with 3SUM over abelian groups and a dichotomy for coordinatewise problems. arXiv:2610.17420, 2026.
\bibitem[P\u{a}t10]{Pat10} M.~P\u{a}tra\c{s}cu. Towards polynomial lower bounds for dynamic problems. In \emph{STOC 2010}, pages 603--610.
\bibitem[RV12]{RV12} L.~Roditty and V.~Vassilevska Williams. Subquadratic time approximation algorithms for the girth. In \emph{SODA 2012}, pages 833--845.
\bibitem[Shr26]{Shr26} shreshth-s. Thin-matrix results. Unrefereed repository, \url{https://github.com/shreshth-s/thin-matrix-results}, accessed 23 October 2026.
\bibitem[SY26]{SY26} B.~Saha and C.~Ye. Simple, faster $(\min,+)$ matrix multiplication and APSP. arXiv:2610.20297, 2026.
\bibitem[VW18]{VW18} V.~Vassilevska Williams and R.~Williams. Subcubic equivalences between path, matrix, and triangle problems. \emph{J.\ ACM} 65(5):27:1--27:38, 2018.
\bibitem[VX20]{VX20a} V.~Vassilevska Williams and Y.~Xu. Monochromatic triangles, triangle listing and APSP. In \emph{FOCS 2020}, pages 786--797. Full version: arXiv:2007.09318.
\bibitem[VXXZ24]{VXXZ24} V.~Vassilevska Williams, Y.~Xu, Z.~Xu, and R.~Zhou. New bounds for matrix multiplication: from alpha to omega. In \emph{SODA 2024}, pages 3792--3835.
\end{thebibliography}

\bigskip\noindent\textsc{Tejasvi Singh Tomar}\par
\noindent\textit{ORCID}: \href{https://orcid.org/0000-0003-4668-3639}{https://orcid.org/0000-0003-4668-3639}
\end{document}