报告题目：Finding large cliques in random and semi-random graphs

报告人：Uriel Feige教授，Weizmann研究院

报告时间：2024年8月23日（星期五）8:30-9:30

报告地点：20-200

报告摘要：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.

报告人简介：Uriel Feige is a professor at the Department of Computer Science and Applied Mathematics of the Weizmann Institute of Science. He also earned his Phd there. He conducted postdoctoral research at Princeton University and at the IBM T.J. Watson Research Center, and later spent a sabbatical at the Compaq Systems Research Center. In 2004-2007, he took leave from the Weizmann Institute to work with Microsoft Research’s Theory Group, and he later served as a part time consultant at Microsoft Research, Israel. His main research areas are algorithms, computational complexity, algorithmic game theory, with a recent focus on fair allocations. He served as Program Committee Chair for STOC (2007) and ICALP (2023, Track A). His work was recognized by some awards, including a Godel Award (2001), a SIAM Outstanding Paper Prize (2005), and a FOCS test of time award (2021).