- Series
- Combinatorics Seminar
- Time
- Friday, December 1, 2017 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Mustazee Rahman – MIT – mustazee@mit.edu – http://math.mit.edu/~mustazee/
- Organizer
- Lutz Warnke
Suppose we want to find the largest independent set or maximal cut in a sparse Erdos-Renyi graph, where the average degree is constant. Many algorithms proceed by way of local decision rules, for instance, the "nibbling" procedure. I will explain a form of local algorithms that captures many of these. I will then explain how these fail to find optimal independent sets or cuts once the average degree of the graph gets large. There are some nice connections to entropy and spin glasses.