SDP, MaxCut, discrepancy and log-rank-conjecture

Abstract:

Semidefinite programming (SDP) is a powerful tool in the design of approximation algorithms. After providing a gentle introduction to the basics of this method,
I will explore a different facet of SDP and show how it can be used to derive short and elegant proofs of both classical and new estimates related to the MaxCut problem and discrepancy theory in graphs and matrices. I also explain how the discrepancy result leads to an improvement in the best-known upper bound on the log-rank conjecture in communication complexity.

Benny Sudakov - Bio

Benny Sudakov received his PhD from Tel Aviv University and has held appointments at Princeton University, the Institute for Advanced Studies,
and UCLA. He is currently a professor of mathematics at ETH Zurich. Sudakov is the recipient of a Sloan Fellowship, an NSF CAREER Award, and a Humboldt Research Award. He is a Member of the Academia Europaea and a Fellow of the American Mathematical Society. Sudakov was a plenary speaker at the 2024 European Congress of Mathematics and an invited speaker at the 2010 International Congress of Mathematicians. His main scientific interests include combinatorics and its applications to other areas of mathematics and computer science