On the constant-depth complexity of k-clique
Benjamin Rossman · 2008
We prove a lower bound of ω(nk/4) on the size of constant-depth circuits solving the k-clique problem on n-vertex graphs (for every constant k). This improves a lower bound of ω(nk/89d2) due to Beame where d is the circuit depth. Our lower bound has the advantage that it does not depend on the constant d in the exponent of n, thus breaking the mold of the traditional size-depth tradeoff.