mlsanityData to 14 Oct 2026

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

arXiv 2101.02312 ↗First posted 7 Jan 2021cs.DS cs.CC math.COcited by 1

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026On the Computational Hardness of Transformerscited by 0