A0191
Title: On counting communities and finding them
Authors: Dana Yang - Cornell University (United States) [presenting]
Abstract: Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? It is shown that the answer is no. In particular, certain hypothesis testing problems between models with different community structures are considered, and it is shown (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities.
