Fine-grained complexity of exact Furthest Pair

Can exact Furthest Pair, which asks for the largest distance among n points, be solved in truly subquadratic time in every slowly growing dimension? The hardness target assumes OVH or SETH and permits any efficiently constructible superconstant dimension.

Why it matters and what counts as progress

Why it matters: The slowly growing dimension regime locates conditional near-quadratic hardness for a basic geometric optimization problem.

What counts as progress: Prove n^(2−o(1)) lower bounds in smaller growing dimensions or give faster algorithms in an explicit dimension regime.

How the problem developed

23 Sept 2020 · Conditional lower bound [1]
Lijie Chen Under SETH, proved near-quadratic hardness for exact Euclidean Furthest Pair in dimension 2^{O(log* n)}.
24 Jun 2026 · Reported claim [2]
Barna Saha, Yinzhan Xu and Christopher Ye Extended the SETH lower bound to every efficiently constructible superconstant dimension d=ω(1); the authors report an AI-discovered proof that they validated and substantially edited.

AI contribution

Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH

Barna Saha, Yinzhan Xu, Christopher Ye

Under OVH or SETH, Saha, Xu and Ye prove n^(2−o(1)) lower bounds for exact Furthest Pair, Bichromatic Closest Pair, Maximum Inner Product and Hopcroft’s problem in every efficiently constructible superconstant dimension.

AI involvementAI-led

ImportanceMajor

Technical verificationFormal (Lean 4 (Lemma 3.1 only) + human)

Human understandingFull