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 

Add to Calendar


Uriel Feige (Weizmann Institute of Science)


Calvin Lab auditorium and Zoom

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.

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