In this talk I will describe lower bounds of n^(k/4) on the average-case complexity of the k-CLIQUE problem (on Erdos-Renyi random graphs at the appropriate threshold) for two classes of circuits: AC0 and monotone circuits. These lower bounds use a similar technique, even though different combinatorial tools are required in the AC0 and monotone settings. Moreover, k/4 is tight (by results of Amano for AC0 and the speaker for monotone). I will also discuss a corollary of the AC0 lower bound concerning first-order logic: we show that the number-of-variables hierarchy is strict in terms of expressive power on ordered graphs (i.e. for every k, there is a sentence involving k variables that is not equivalent on ordered graphs to any sentence involving k-1 variables). Prior to this result, it was unknown whether 3 variables suffice to define any first-order property of ordered graphs.