Is It Easier to Count Communities Than Find Them?

Explore a 47-minute lecture on community detection in random graph models presented by Cynthia Rush from Columbia University at IPAM's EnCORE Workshop. Delve into the intriguing question of whether inferring properties of community structures is computationally easier than actually finding the communities themselves. Examine the landscape of statistical and computational phase transitions in detecting and recovering community structure. Learn about hypothesis testing problems between models with different community structures and discover why testing between two options is as challenging as identifying the communities. Gain insights into the first computational lower bounds for testing between two different "planted" distributions, expanding beyond previous comparisons with i.i.d. "null" distributions. Understand the implications of this joint research work with Fiona Skerman, Alexander S. Wein, and Dana Yang in the field of graph theory and community detection algorithms.