Fine-grained complexity of Maximum Inner Product

For exact Maximum Inner Product on point sets in efficiently constructible superconstant dimension, can an n^(2−o(1)) lower bound be proved under OVH or SETH?

Why it matters and what counts as progress

Why it matters: It asks whether conditional quadratic hardness persists throughout the smaller-dimensional range left by earlier reductions.

What counts as progress: Extend exact maximum-inner-product hardness to smaller dimensions under OVH or SETH, preserving efficient dimension construction.

How the problem developed

23 Sept 2020 · Conditional lower bound [1]
Lijie Chen Under SETH, proved near-quadratic hardness for exact integer Maximum Inner Product 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