CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits

Levente Bodnar

This paper shows that calculating $k$-CLIQUE on $n$ vertex graphs, requires the AND of at least $2^{n/4k}$ monotone, constant-depth, and polynomial-sized circuits, for sufficiently…