k-Clique on Random Graphs
by Ben Rossman.
Oded's comments
Needless to say, the lower bound refers to the average-case
complexity of graphs drawn from the threshold probability.
The fact that these lower bounds are tight (as demonstarted
by matching upper bounds) is striking. Same for the fact
the the average-lower bound significantly improves the best
previously known lower bounds for worst-case in the AC0 case.
The original abstract
I will discuss results, of myself (lower bound) and Kazuyuki Amano
(upper bound), showing that the average-case complexity of k-CLIQUE
(for constant k) is n^(k/4 + O(1)) for AC^0 circuits as well as
monotone circuits.
Back to
list of Oded's choices.