# The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs

arXiv: https://arxiv.org/abs/1903.08247 · HTML: https://mlsanity.com/paper/1903.08247/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2019.

## Built on by (most cited first, 3 of 3)

- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Low-degree phase transitions for detecting a planted clique in sublinear time](https://mlsanity.com/paper/2402.05451/) (2024)

## Abstract (arXiv)

We consider the problem of counting k-cliques in s-uniform Erdos-Renyi hypergraphs G(n,c,s) with edge density c, and show that its fine-grained average-case complexity can be based on its worst-case complexity. We prove the following: 1. Dense Erdos-Renyi graphs and hypergraphs: Counting k-cliques on G(n,c,s) with k and c constant matches its worst-case time complexity up to a polylog(n) factor. Assuming randomized ETH, it takes nOmega(k) time to count k-cliques in G(n,c,s) if k and c are constant. 2. Sparse Erdos-Renyi graphs and hypergraphs: When c = Theta(n-α), we give several algorithms exploiting the sparsity of G(n, c, s) that are faster than the best known worst-case algorithms. Complementing this, based on a fine-grained worst-case assumption, our results imply a different average-case phase diagram for each fixed α depicting a tradeoff between a runtime lower bound and k. Surprisingly, in the hypergraph case (s ≥ 3), these lower bounds are tight against our algorithms exactly when c is above the ErdHos-R'enyi k-clique percolation threshold. This is the first worst-case-to-average-case hardness reduction for a problem on ErdHos-R'enyi hypergraphs that we are aware of. We also give a variant of our result for computing the parity of the k-clique count that tolerates higher error probability.