Probability and Statistics Seminar: Approximate counting and sampling via local central limit theorems

Friday, September 3 at 3:30pm to 4:30pm

This is a past event.
Virtual Event


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)

 

Dial-In Information

Zoom Meeting: https://usc.zoom.us/j/97697301086?pwd=ZU9oRFRiM0F3L2lNN1Ric0FqMFBzdz09

Meeting ID: 976 9730 1086
Passcode: 833477

Event Type

Lecture / Talk / Workshop

Department
Mathematics
Add this to your calendar

Recent Activity