Theory Lunch This Thursday (12:00 PM, 09/17, GCS 502c)
15 views
Skip to first unread message
Fatih Erdem Kızılkaya
Sep 14, 2026, 8:08:21 PMSep 14
to csth...@usc.edu, USC Theory Group, usc-t...@googlegroups.com
Hi all,
Please join us for Theory Lunch this Thursday, 09/17, at 12:00 PM in GCS 502c. This week, Vasilis will give the following talk:
Title: Finding Diverse Bases in Matroids
Abstract: We study the geometry of matroids via the diameter of the metric space defined by the matroid's bases. Given a matroid, we consider its basis-exchange graph and ask if its diameter can be approximated by sampling two uniformly random bases. As our main result we show that the expected distance of two uniformly sampled bases is always at least 1/16 of the matroid's diameter. We then turn to the problem of finding k ≥ 2 maximally-diverse bases of a matroid. When k = 2 the problem is solvable via matroid intersection. However, for k ≥ 3 no polynomial-time approximation algorithm or hardness result is known even for the well-studied case of finding diverse spanning trees of a graph (i.e., in a graphic matroid). We first show that sampling k ≥ 3 bases does not provide an O(1) approximation to the above problem: in fact, it provides a tight Θ(log k) approximation. We then briefly discuss a novel polynomial-time 1/6-approximation algorithm for the k-diversity problem in arbitrary matroids, as well as some hardness results. Finally, if there's time, we will briefly talk about some stronger guarantees for the important special cases of partition matroids and graphic matroids of constant arboricity.
---
The meeting will also be hosted on Zoom:
https://usc.zoom.us/j/97079961216
Meeting ID: 970 7996 1216
Best,
Fatih
Please join us for Theory Lunch this Thursday, 09/17, at 12:00 PM in GCS 502c. This week, Vasilis will give the following talk:
Title: Finding Diverse Bases in Matroids
Abstract: We study the geometry of matroids via the diameter of the metric space defined by the matroid's bases. Given a matroid, we consider its basis-exchange graph and ask if its diameter can be approximated by sampling two uniformly random bases. As our main result we show that the expected distance of two uniformly sampled bases is always at least 1/16 of the matroid's diameter. We then turn to the problem of finding k ≥ 2 maximally-diverse bases of a matroid. When k = 2 the problem is solvable via matroid intersection. However, for k ≥ 3 no polynomial-time approximation algorithm or hardness result is known even for the well-studied case of finding diverse spanning trees of a graph (i.e., in a graphic matroid). We first show that sampling k ≥ 3 bases does not provide an O(1) approximation to the above problem: in fact, it provides a tight Θ(log k) approximation. We then briefly discuss a novel polynomial-time 1/6-approximation algorithm for the k-diversity problem in arbitrary matroids, as well as some hardness results. Finally, if there's time, we will briefly talk about some stronger guarantees for the important special cases of partition matroids and graphic matroids of constant arboricity.
---
The meeting will also be hosted on Zoom:
https://usc.zoom.us/j/97079961216
Meeting ID: 970 7996 1216
Best,
Fatih
Reply all
Reply to author
Forward
0 new messages