Speaker:

Giorgos Mousa

Time:

• 16:20-17:20 Beijing Time

• March 28, 2025 (Friday)

Venue:

518, Research Building 4

Abstract:

The broken circuit complex is a generalization of the matroid independence complex. Given that the exchange walk over the bases of a matroid is fast-mixing [Anari et al., 2019], we are interested in whether the exchange walks over the broken circuit complex are also fast-mixing. This may enable us, e.g., to approximately uniformly sample and count the number of acyclic orientations of a graph, which is a #P-hard problem of unknown approximability.

Speaker Bio:

Giorgos Mousa obtained his PhD from the University of Edinburgh, where he worked with Professor Heng Guo in the Laboratory for the Foundations of Computer Science. His research interests include matroid theory, Markov chains, and sampling and counting problems.