Hardness of clique approximation for monotone circuits

Jarosław Błasiok, Linus Meierhöfer

We consider a problem of approximating the size of the largest clique in a graph, with a monotone circuit. Concretely, we focus on distinguishing a random Erdős-Renyi graph $\mathc…