Friday, September 3 at 3:30pm to 4:30pm
There will be a projector screen in KAP 414 for those who would like to gather and watch the talk. Note the speaker will not be present in KAP 414.
Mehtaab Sawhney, MIT
Abstract: We give determinisitc approximate counting algorithms for the number of matchings and independent sets of a given size in bounded degree graphs. For matchings, the algorithm applies to any size bounded away from the maximum by a constant factor; for independent sets the algorithm applies to sizes up to the NP-hardness threshold. Our results are based on exploiting local central limit theorems as an algorithmic tool. For our results for independent sets, we prove a new local central limit theorem for the hard-core model. (with Vishesh Jain, Will Perkins, and Ashwin Sah)
Meeting ID: 976 9730 1086