Location: Gilman 132
When: September 21st at 1:30 p.m.
Title: Counting independent sets in dense bipartite graphs
Abstract: Originating in physics, counting independent sets is one of the most studied problems in approximate counting and related fields. While it is hard in general, restricted to bipartite graphs the problem is fascinating and its complexity remains unknown. We will motivate counting independent sets and describe a few recent results that give a polynomial-time algorithm on dense, regular bipartite graphs. The methods we use are interesting in their own right, including graph containers and subspace enumeration.
Bio: Dr. Ewan Davies is an assistant professor in the Department of Computer Science at Colorado State University. He studied mathematics at the University of Cambridge and the London School of Economics and Political Science, and his research interests include algorithms, extremal graph theory and statistical physics. He studies high-dimensional combinatorial spaces and uses intuition from physics and graph theory to design efficient approximation algorithms.
Zoom link: https://wse.zoom.us/j/94601022340