Explore the intricacies of finding large cliques in random and semi-random graphs in this Richard M. Karp Distinguished Lecture delivered by Uriel Feige from the Weizmann Institute of Science. Delve into the click problem, examining the model and proof while considering constructive arguments. Investigate algorithms for finding clicks and understand why the click is not a fixed parameter. Follow the proof in polynomial time and review the algorithm, paradigm, and hypothesis. Gain valuable insights into this complex topic through a comprehensive one-hour presentation that covers introduction, summary, and in-depth analysis of the subject matter.
Finding Large Cliques in Random and Semi-Random Graphs
Overview
Syllabus
Introduction
The Click Problem
The Model
Proof
Constructive Arguments
Algorithms for finding clicks
Click is not fixed parameter
Proof in polynomial time
Summary
Algorithm Review
Paradigm
Hypothesis
Taught by
Simons Institute
