The Average-Case Complexity of Counting Cliques in Erdoős–Reényi Hypergraphs
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.
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}
}
EUVIMED