# 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n4/3

arXiv: https://arxiv.org/abs/2101.02312 · HTML: https://mlsanity.com/paper/2101.02312/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jan 2021.

## Built on by (most cited first, 1 of 1)

- [On the Computational Hardness of Transformers](https://mlsanity.com/paper/2603.11332/) (2026)

## Abstract (arXiv)

We show, assuming the Strong Exponential Time Hypothesis, that for every varepsilon > 0, approximating undirected unweighted Diameter on n-vertex n1+o(1)-edge graphs within ratio 7/4 - varepsilon requires n4/3 - o(1) time. This is the first result that conditionally rules out a near-linear time 5/3-approximation for undirected Diameter.