Singla preprint claims matroid secretary conjecture resolved
TL;DR
- Sahil Singla has posted an arXiv preprint titled 'The Matroid Secretary Conjecture is True,' claiming a full resolution.
- The algorithm is stated to accept each element of the offline optimum with probability at least 1/4.
- It requires only the element count in advance and independence-oracle access to arrived elements, not the matroid itself.
Sahil Singla claims to have resolved the matroid secretary conjecture in a preprint posted to arXiv titled "The Matroid Secretary Conjecture is True."
The abstract reports an online algorithm that "accepts each element of the offline optimum with probability at least 1/4." The algorithm, per the abstract, "only needs the number of elements in advance and independence-oracle access to subsets of already-arrived elements; it does not need to know the matroid upfront."
The v1 preprint is dated September 13, 2026 and filed under cs.DS and cs.GT. Two researchers we track shared the link the same day it went up.
Shared on Bluesky by 2 AI experts
-
Aaron Roth @aaroth.bsky.social
A world without open problems Here are some that fell today: K-server: arxiv.org/abs/2609.15979 Matroid Secretary: arxiv.org/abs/2609.145... Matrix Spencer: arxiv.org/abs/2609.15025 (Well Matrix Spencer was maybe also …
View on Bluesky →
Originally reported by arxiv.org
Read the original article →Original headline: The Matroid Secretary Conjecture is True