AI-assisted proofs reach the optimal secretary guarantee for all linear matroids
Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, and Danny Mittal posted a proof of the strong matroid secretary conjecture for every linear matroid, establishing the optimal 1/e competitive guarantee for this broad class of online selection problems. The authors say GPT-5.6 Sol and GPT-6 Astra were essential to the construction and that they independently checked the resulting proofs; a second group subsequently posted essentially the same construction, also obtained with Astra.
Why it made the cut: This is a substantive theoretical advance with explicit researcher attribution of AI's role and corroboration from a separate expert group, rather than a model's unsupported claim to solve a problem. Both accounts are preprints, the full strong conjecture for arbitrary matroids remains outside the proved linear-matroid result, and the coincident constructions raise unresolved provenance questions without establishing that private conversations were shared.
First paper · Concurrent paper · Official research-group announcement
Link to this post