MATH Seminar

Title: Containers, cluster expansion, phase transitions and algorithms
Seminar: Discrete Math
Speaker: Aditya Potukuchi of University of Illinois - Chicago
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2022-01-13 at 10:00AM
Venue: MSC W201
Download Flyer
Abstract: The main focus of the talk will revolve around the following problem: Given a d-regular bipartite graph G on n vertices, output approximately the number of independent sets in G. This problem is well-studied in combinatorics and theoretical computer science. In combinatorics, we would like asymptotic expressions for certain families of graphs. In algorithms, this problem captures the difficulty of several counting and sampling problems and its computational complexity is currently unknown. I will describe some recent algorithmic progress on this problem, in particular, running time improvement and efficient algorithms if G satisfies some weak expansion conditions. The techniques combine graph container methods with cluster expansion methods from statistical physics and involve understanding certain phase transitions. I will also talk about using these techniques to approximately count the number of independent sets of a given size in the discrete hypercube, and point towards future applications. The talk is targeted at a broad audience, and no specialized knowledge of any of the mentioned topics is assumed. The talk is based on results joint with Matthew Jenssen and Will Perkins.