SDP, MaxCut, Discrepancy, and the Log-Rank Conjecture

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.

Building on this, I will demonstrate how these results lead to an improved upper bound on the celebrated log-rank conjecture in communication complexity.