Fine-grained complexity of Bichromatic Closest Pair

How quickly can exact bichromatic closest pair be solved in a dimension that grows arbitrarily slowly with input size n? The target is a conditional n^(2−o(1)) lower bound for every efficiently constructible superconstant dimension, assuming OVH or SETH.

Why it matters and what counts as progress

Why it matters: The superconstant-dimension regime tests where geometric closest-pair problems acquire conditional near-quadratic hardness.

What counts as progress: Give a reduction covering smaller growing dimensions, or an algorithm improving the quadratic exponent under a precisely stated dimension regime.

How the problem developed

23 Sept 2020 · Conditional lower bound [1]
Lijie Chen Under SETH, proved near-quadratic lower bounds for bichromatic Euclidean closest 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