EUVIMEDEUVIMED entdecken
Crossref

The Average-Case Complexity of Counting Cliques in Erdoős–Reényi Hypergraphs

Enric Boix-Adseraà, Matthew Brennan, Guy Bresler

SIAM Journal on Computing · 31.08.2025 · 54 (4) · FOCS19-39-FOCS19-80

DOI: 10.1137/20m1316044 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 14.09.2021. Verfasst von Enric Boix-Adseraà und 2 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 76 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the problem of counting [Formula: see text]-cliques in [Formula: see text]-uniform Erdős–Rényi hypergraphs [Formula: see text] with edge density [Formula: see text] and show that its fine-grained average-case complexity can be based on its worst-case complexity. We prove the following: (1) Dense Erdős–Rényi graphs and hypergraphs: Counting [Formula: see text]-cliques on [Formula: see text] with [Formula: see text] and [Formula: see text] constant matches its worst-case complexity up to a [Formula: see text] factor. Assuming randomized ETH, it takes [Formula: see text] time to count [Formula: see text]-cliques in [Formula: see text] if [Formula: see text] and [Formula: see text] are constant. (2) Sparse Erdős–Rényi graphs and hypergraphs: When [Formula: see text], we give several algorithms exploiting the sparsity of [Formula: see text] that are faster than the best known worst-case algorithms. Complementing this, based on a fine-grained worst-case assumption, our reduction implies a different average-case phase diagram for each fixed [Formula: see text] depicting a tradeoff between a runtime lower bound and [Formula: see text]. Surprisingly, in the hypergraph case ([Formula: see text]), these lower bounds are tight against our algorithms exactly when [Formula: see text] is above the Erdős–Rényi [Formula: see text]-clique percolation threshold. Our reduction yields the first known average-case hardness result on Erdős–Rényi hypergraphs based on worst-case hardness conjectures. We also give a variant of our worst-case to average-case reduction for computing the parity of the [Formula: see text]-clique count that requires a milder assumption on the error probability of the blackbox solving the problem on [Formula: see text].

Zitieren

APA

Boix-Adseraà, E., Brennan, M., & Bresler, G. (2025). The Average-Case Complexity of Counting Cliques in Erdoős–Reényi Hypergraphs. SIAM Journal on Computing, 54(4), FOCS19-39-FOCS19-80. https://doi.org/10.1137/20m1316044

Vancouver

Boix-Adseraà E, Brennan M, Bresler G. The Average-Case Complexity of Counting Cliques in Erdoős–Reényi Hypergraphs. SIAM Journal on Computing. 2025;54(4):FOCS19-39-FOCS19-80. doi:10.1137/20m1316044

BibTeX
@article{BoixAdsera2025,
  author = {Boix-Adseraà, Enric and Brennan, Matthew and Bresler, Guy},
  title = {The Average-Case Complexity of Counting Cliques in Erdoős–Reényi Hypergraphs},
  journal = {SIAM Journal on Computing},
  year = {2025},
  volume = {54},
  number = {4},
  pages = {FOCS19--39--FOCS19--80},
  doi = {10.1137/20m1316044}
}
Kostenlos starten →