The Monotone Complexity of $k$-Clique on Random Graphs
Benjamin Rossman · SIAM Journal on Computing · 2014
We present lower and upper bounds showing that the average-case complexity of the $k$-Clique problem on monotone circuits is $n^{k/4 + O(1)}$. Similar bounds for $\mathsf{AC}^0$ circuits were shown in Rossman [Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 721--730] and Amano [Comput. Complexity, 19 (2010), pp. 183--210].