Talk information

Date: Sunday, December 31, 2023
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Benny Sudakov (ETH Zurich)
Title: SDP, MaxCut, discrepancy and log-rank-conjecture

Abstract:

Semidefinite programming (SDP) is a powerful method used in many important approximation algorithms. In this talk, I discuss a different aspect of SDP and demonstrate how it can be employed to offer concise proofs for several well-known and new estimates related to MaxCut, as well as the discrepancy of graphs and matrices. I also explain how the discrepancy result leads to an improvement in Lovett’s best-known upper bound on the log-rank conjecture.