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.