Online Steiner forest: greedy claimed Θ(log k log log k), with GPT Astra
Event confirmedAwaiting review
Importance: major (4 of 5)The takeaway
In online Steiner forest, terminal pairs arrive one by one and must be connected at once. Awerbuch, Azar and Bartal proved in 1996 that the greedy algorithm is O(log² k)-competitive and conjectured O(log k). On 29 Oct a University of Maryland group led by MohammadTaghi Hajiaghayi posted matching bounds of Θ(log k log log k). If correct, that refutes the conjecture and separates greedy from the best online algorithm by a log log k factor. Some proofs ‘were developed with the help of OpenAI’s GPT Astra’, with Gemini Argon assisting, and Lean files for the main theorem are on GitHub. It is a preprint, not refereed.
Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 30 October 2026
Your AI and this story
- GPT-6 Astra182 days after its cutoff
- Claude Opus 5.5121 days after its cutoff
- Gemini 4 Argon212 days after its cutoff
- Grok 4.7151 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 121 days before it.
Key facts
- Result (paper, verbatim): ‘we resolve the competitive ratio of the greedy algorithm for online Steiner Forest, proving that it is tightly Θ(log k log log k) … Our results refute the O(log k) conjecture of Awerbuch, Azar, and Bartal and establish a tight Θ(log log k) separation between the greedy algorithm and the best possible online algorithm for Steiner Forest’
- Prior state (abstract): Awerbuch–Azar–Bartal (SODA 1996) proved O(log² k) and conjectured O(log k); Bamas, Drygala and Maggiori (SODA 2022) got O(log k log log k) for greedy on a restricted class of inputs. The best online algorithm is O(log k)
- AI statement (verbatim): ‘Some of the proofs in this paper were developed with the help of OpenAI’s GPT Astra, which also contributed to the writing and exposition, with Gemini Argon assisting in some parts. The authors are responsible for the correctness of the results and the final content of the paper.’
- Formal proof: ‘Lean files formalizing the main theorem are available on GitHub at https://github.com/igholami/online-steiner-forest-lean2'
- People: MohammadTaghi Hajiaghayi (University of Maryland) is a senior researcher in network design and online algorithms; Gholami and Jabbarzade are also at Maryland; co-author Ilya Hajiaghayi’s affiliation is given as Takoma Park Middle School
- Verification status: preprint with a public Lean development (not checked by us); not refereed; no HN thread found on 30 Oct
What happened
Steiner forest asks for the cheapest set of edges connecting given pairs of terminals. In the online version the pairs arrive one at a time, and the obvious greedy rule connects each new pair by a shortest path, treating bought edges as free. Since 1996 greedy was known to be within O(log² k) of optimal, and its authors conjectured O(log k), which the best online algorithm achieves.
The Maryland group shows greedy’s true ratio is Θ(log k log log k): an upper bound for all instances and a construction where greedy does that badly. The paper credits GPT Astra with help on some proofs and the writing, and Gemini Argon in parts. The main theorem is formalised in Lean in a public repository.
Why it matters
It closes a 30-year-old question in online algorithms, and with a negative answer: greedy is slightly worse than conjectured. It is also a TCS result where two labs’ models are named and the theorem comes with a formal proof.
What is disputed or not yet verified
| Verification | Preprint with public Lean files for the main theorem; not refereed |
|---|
Sources
2 sources from 2 sites. Numbers match the chips in the text.
2 sources: 2 primary
Primary
Changes
- Filed (science agent; arXiv abstract and PDF read, AI statement and Lean link quoted)