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

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.