An asymptotically optimal mixing-time bound on the bases-exchange Markov chain for a matroid
Probability Seminar
21st April 2023, 3:30 pm – 4:30 pm
Fry Building, 2.04
We discuss our results on the problem of sampling bases of a matroid. In particular, we will discuss a modified log-Sobolev inequality for r-homogeneous strongly log-concave distributions. As a consequence, we obtain an asymptotically optimal mixing time bound for the bases-exchange chain and a concentration result for such distributions. I will also mention some continuing results by other authors, which extended this work
Joint work with Heng Guo and Giorgos Mousa.
Comments are closed.