for this workshop
Connecting communities via the block model
American Institute of Mathematics, San Jose, California
Emmanuel Abbe, Laurent Massoulie, and Elchanan Mossel
This workshop, sponsored by AIM and the NSF, will focus on the goal of leveraging newly established connections and techniques to study new challenges involving inference of combinatorial structures both in the context of network models and beyond. Some of the thematics covered are:
- Statistical vs. computational tradeoffs.
This has been a major theme of research in inference of planted models starting with the hidden clique problem where the problem in information theoretically solvable for much smaller cliques than what can be found algorithmically. Understanding the limitation of algorithms in other planted models has a physics interpretation. Understanding better such phenomena would benefit from a diversified workshop.
Interestingly, the study of phase transition for random and planted problems have resulted in new algorithms. For constraint satisfcation problems such an algorithm is survey propagation while in the context of the block model, linear algebra algorithms based on nonbacktracking operators proved useful. More algorithmic developments are expected to emerge from this quest.
- Beyond block models.
The SBM is a canonical model for community detection, and its extensions allows one to capture various important questions in complex networks and machine learning. The workshop will also focus on extensions of the basic model, such as graphons and low-rank approximation models, and more generally on the inference of combinatorial structures.
The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.
The deadline to apply for support to participate in this workshop has passed.
For more information email firstname.lastname@example.org