#
Connecting communities via the block model

May 22 to May 26, 2017
at the

American Institute of Mathematics,
San Jose, California

organized by

Emmanuel Abbe,
Laurent Massoulie,
and Elchanan Mossel

## Original Announcement

This workshop 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.

- Algorithms.
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.

## Material from the workshop

A list of participants.
The workshop schedule.

A report on the workshop activities.

A list of open problems.

Papers arising from the workshop: