1 Search Results for "Rush, Cynthia"


Document
Is It Easier to Count Communities Than Find Them?

Authors: Cynthia Rush, Fiona Skerman, Alexander S. Wein, and Dana Yang

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


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? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities. In addition, our methods give the first computational lower bounds for testing between two different "planted" distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. "null" distribution.

Cite as

Cynthia Rush, Fiona Skerman, Alexander S. Wein, and Dana Yang. Is It Easier to Count Communities Than Find Them?. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 94:1-94:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{rush_et_al:LIPIcs.ITCS.2023.94,
  author =	{Rush, Cynthia and Skerman, Fiona and Wein, Alexander S. and Yang, Dana},
  title =	{{Is It Easier to Count Communities Than Find Them?}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{94:1--94:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.94},
  URN =		{urn:nbn:de:0030-drops-175970},
  doi =		{10.4230/LIPIcs.ITCS.2023.94},
  annote =	{Keywords: Community detection, Hypothesis testing, Low-degree polynomials}
}
  • Refine by Author
  • 1 Rush, Cynthia
  • 1 Skerman, Fiona
  • 1 Wein, Alexander S.
  • 1 Yang, Dana

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Random network models

  • Refine by Keyword
  • 1 Community detection
  • 1 Hypothesis testing
  • 1 Low-degree polynomials

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail