The Average-Case Complexity of Counting Cliques in Erdoős–Reényi Hypergraphs
Enric Boix-Adserà, Matthew Brennan, Guy Bresler · SIAM Journal on Computing · 2021
Abstract. 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].