The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs
Enric Boix-Adserà, Matthew Brennan, Guy Bresler · 2019
The complexity of clique problems on Erdos-Renyi random graphs has become a central topic in average-case complexity. Algorithmic phase transitions in these problems have been shown to have broad connections ranging from mixing of Markov chains and statistical physics to information-computation gaps in high-dimensional statistics. 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 worstcase complexity. We prove the following: 1) Dense Erdos-Renyi hypergraphs: Counting k-cliques on G(n, c, s) with k and c constant matches its worst-case complexity up to a polylog(n) factor. Assuming ETH, it takes nΩ(k)time to count k-cliques in G(n, c, s) if k and c are constant. 2)Sparse Erdos-Renyi hypergraphs: When c = Θ(n-α), for each fixed α our reduction yields different average-case phase diagrams depicting a tradeoff between runtime and k. Assuming the best known worst-case algorithms are optimal, in the graph case of s = 2, we establish that the exponent in n of the optimal running time for k-clique counting in G(n, c, s) is ωk/3 - Cα(k/2) + Ok,α(1), where ω/9 ≤ C ≤ 1 and w is the matrix multiplication constant. In the hypergraph case of s ≥ 3, we show a lower bound at the exponent of k-α(k/s)+Ok,α(1) which surprisingly is s tight against algorithmic achievability exactly for the set of c above the Erdos-Renyi k-clique percolation threshold. Our reduction yields the first known average-case hardness result on Erdos-Renyi hypergraphs based on a worst-case hardness assumption. We also analyze several natural algorithms for counting k-cliques in G(n, c, s) that establish our upper bounds in the sparse case c = Θ(n-α).