Matroid secretary conjecture resolved, with GPT Astra
Awaiting review
Importance: major (4 of 5)The takeaway
Sahil Singla posted “The Matroid Secretary Conjecture is True” (arXiv 2609.14555, 13 Sep 2026): a 4-probability-competitive online algorithm for every matroid, settling Babaioff–Immorlica–Kleinberg’s 2007 conjecture.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 9 November 2026
Your AI and this story
- GPT-6 Astra136 days after its cutoff
- Claude Opus 5.575 days after its cutoff
- Gemini 4 Argon166 days after its cutoff
- Grok 4.7105 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 75 days before it.
Key facts
- Conjecture: Babaioff, Immorlica and Kleinberg (SODA 2007) asked for an O(1)-competitive secretary algorithm on every matroid; the strong form asks for ratio e, as for a single item
- Singla, arXiv 2609.14555 (v1 13 Sep 2026): accepts each element of the offline optimum with probability at least 1/4; needs only the number of elements and an independence oracle on arrived elements
- Abdi, Banihashem, Hajiaghayi, Mittal, arXiv 2609.19118 (16 Sep): strong conjecture for linear matroids via a finite LP; Bérczi, Dughmi, Livanos & Soto, 2609.20797, independently for linear matroids with GPT Astra
- Merged paper 2611.08869 (9 Nov): ratio e for every matroid (ordinal, expected polynomially many queries) and ratio 2 single-sample prophet inequality; merges Singla, ABHM and Huang’s preprint
- AI statement (2611.08869): ‘Interactions with models available through ChatGPT Pro, especially GPT Astra, were used in obtaining the main algorithmic guarantees, including Theorems 2.2, 3.1, 5.2 and 7.2; GPT Sol 5.6 was also used’; the LP of Section 4 was ‘devised and carried out without AI models’; ‘The authors checked the resulting proofs’
- Status: preprints, no peer review; code at github.com/TlatoaniHJ/MatroidSecretary
What happened
On 13 Sep 2026 Sahil Singla posted arXiv 2609.145552, “The Matroid Secretary Conjecture is True”, giving an online algorithm that accepts each element of the offline optimum with probability at least 1/4. Within days, Abdi, Banihashem, Hajiaghayi and Mittal3 and Bérczi, Dughmi, Livanos and Soto4 proved the strong (ratio e) conjecture for linear matroids. A tracker also recorded a preprint by Zhiyi Huang claiming ratio e for every matroid.
On 9 Nov the groups posted a merged paper, arXiv 2611.088691, claiming the strong conjecture for every matroid and the optimal single-sample matroid prophet inequality. Its AI statement: “The results came from combining the authors’ direction with the technical capabilities of AI models … Interactions with models available through ChatGPT Pro, especially GPT Astra, were used in obtaining the main algorithmic guarantees, including Theorems 2.2, 3.1, 5.2 and 7.2.” It is not stated in this entry whether Singla’s v1 itself used AI; the September preprint was missed by our sweep and found only through the merged paper.
Why it matters
The matroid secretary problem was one of the best-known open problems in online algorithms. The result is unrefereed; no expert commentary was found on 9 Nov.
What is disputed or not yet verified
| Verification | Unrefereed preprints; authors’ checks |
|---|
Sources
7 sources from 4 sites. Numbers match the chips in the text.
7 sources: 5 primary, 1 press, 1 reaction
Primary
- Abdi, Banihashem, Hajiaghayi, Huang, Mittal, Singla: As Easy as Rank One (arXiv 2611.08869)arxiv.org, paper
- Singla: The Matroid Secretary Conjecture is True (arXiv 2609.14555)arxiv.org, paper
- Abdi, Banihashem, Hajiaghayi, Mittal: On the Strong Matroid Secretary Conjecture and Beyond (arXiv 2609.19118)arxiv.org, paper
- Bérczi, Dughmi, Livanos, Soto: The Strong Secretary Conjecture is True for Linear Matroids (arXiv 2609.20797)arxiv.org, paper
- Implementation (GitHub)github.com, code
Press
- AI Weekly: Singla preprint claims matroid secretary conjecture resolvedaiweekly.co, press
Reactions
- Breakthrough Tracker record (kingy.ai)kingy.ai, discussion
Changes
- Filed (missed in September)