Events Fall 2021

# Richard M. Karp Distinguished Lecture — Finding Large Cliques in Random and Semi-Random Graphs

Nov 1, 2021 4:00 pm – 5:00 pm

In random graphs on $n$ vertices, where every edge is present independently with probability $1/2$, 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.