"False"
Skip to content
printicon
Main menu hidden.

Sharing Session 15

Klara Stokes, “You have used matroids this week: the structure behind greedy, fair and diverse selection” 

 

Speaker: Klara Stokes, Department of Mathematics and Mathematical Statistics 

Title: You have used matroids this week: the structure behind greedy, fair and diverse selection 

Abstract: 
Why does a greedy strategy find a minimum spanning tree, but fail on knapsack? The answer is the combinatorial structure, the matroid; it marks one of the cleanest boundaries in algorithm design. Greedy is optimal on exactly the problems that are matroids. 

This interactive talk argues that matroids deserve a place in every computer scientist’s toolkit, and that they matter even more in the age of AI. Selecting training data under per-class quotas, retrieving diverse documents for RAG, and enforcing fairness constraints in rankings all have matroids underneath, usually unrecognized. Seeing that structure gives you algorithms with guarantees instead of heuristics. 

We will start from the definition and a small collection of examples. The highlight is a recent success story. A 30-year-old conjecture on sampling the bases of a matroid was resolved through log-concavity, an idea rooted in the Hodge theory behind June Huh’s Fields Medal. That work produced efficient sampling algorithms and a technique that has since reshaped MCMC analysis. 

No prior knowledge of matroids is assumed. You will hopefully leave with a simple checklist for spotting matroid structure in your own problems. 

 

Latest update: 2026-11-17