Fine-grained complexity of Hopcroft’s problem

Hopcroft’s problem asks whether two given sets of vectors contain an orthogonal pair. The scoped target is an n^(2−o(1)) lower bound for exact solution in every efficiently constructible superconstant dimension, assuming OVH or SETH.

Why it matters and what counts as progress

Why it matters: It asks whether the quadratic hardness barrier persists in dimensions below those covered by earlier reductions; the conclusion remains conditional on a fine-grained hypothesis.

What counts as progress: Extend conditional hardness to smaller superconstant dimensions while keeping the construction efficient and the OVH or SETH assumption explicit.

How the problem developed

23 Sept 2020 · Conditional lower bound [1]
Lijie Chen Under SETH, proved near-quadratic hardness for Hopcroft’s problem 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