Quadratic-Time Hardness of Furthest Pair in Superconstant Dimension
Furthest Pair and its relatives admit algorithms, making them the standard examples of barely subquadratic computation, and whether that is optimal in superconstant dimension was open. Under SETH it is: Furthest Pair requires quadratic time once the dimension is superconstant.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Fine-grained complexity
- Posed by
- fine-grained complexity literature
- Year posed
- —
- Years open
- —
- Solved
- 2026-06-24
- Model
- ChatGPT 5.5 Pro (with Codex, Claude Opus, Gemini for feedback)
- Vendor
- OpenAI / Anthropic / Google
- Collaborators
- Barna Saha, Yinzhan Xu, Christopher Ye
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 20 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The paper states the proof was initially discovered by ChatGPT 5.5 Pro, that the initial prompt was essential, and that other systems were used to generate feedback on it. The authors validated and substantially edited the proof to improve it.
Verification
arXiv preprint; not yet peer-reviewed.
Source
arXiv:2606.25887 - Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH