BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UIC
BEGIN:VEVENT
UID:2021102504015120211018T14000020211018T14500061762c2fe92c0@uic.edu
CATEGORIES:MEETING
STATUS:TENTATIVE
DTSTAMP:20211024T101803
DTSTART:20211018T140000
DTEND:20211018T145000
SUMMARY:Combinatorics and Probability Seminar: Faster algorithms for counting independent sets in regular bipartite graphs, by Aditya Potukuchi
DESCRIPTION:Aditya Potukuchi (UIC): Faster algorithms for counting independent sets in regular bipartite graphs I will present an algorithm that takes as input a d-regular bipartite graph G, runs in time exp(O(n/d log^3 d)), and outputs w.h.p., a (1 + o(1))-approximation to the number of independent sets in G. As a by-product of the intermediate steps to this algorithm, We also obtain, for fixed d, an FPTAS to approximate the number of independent sets in d-regular bipartite ``expanding'' graphs. More than the result itself, I will focus on the techniques used, which combine combinatorial methods (graph containers) with statistical physics methods (abstract polymer models and cluster expansion) and mention other recent applications. I will start from the basics, and no prior knowledge of any of the topics is assumed. Joint work with Matthew Jenssen and Will Perkins. Please click here to make changes to, or delete, this seminar announcement.
LOCATION:636 SEO Chicago IL
CLASS:PRIVATE
END:VEVENT
END:VCALENDAR