In random graphs on n vertices, where every edge is present independently with probability ½, the largest clique is almost surely of size roughly 2 log n. In such graphs, cliques of size log n can be found by a greedy algorithm. Is there some epsilon > 0 such that cliques of size (1 + epsilon) log n can be found efficiently? This question, raised by Karp in 1976, remains open. This talk will discuss selected parts of the large body of research that was motivated by this open question.

If you require accommodation for communication, please contact our Access Coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.