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

Enric Boix-Adserà, Matthew Brennan, Guy Bresler

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…