MaxCut, Orthonormal Representations, and Extension Complexity of Polytopes

This lecture by Igor Balla explores several extremal problems at the intersection of combinatorics and linear algebra, focusing on MaxCut, the Lovász theta function, minimum semidefinite rank, and extension complexity of polytopes. Learn how a bipartite generalization of Alon and Szegedy's nearly orthogonal vectors provides strong bounds for these problems, with results from joint work with Letzter, Sudakov, and Janzer. The speaker, a Strauch Postdoctoral Fellow at the Simons Laufer Mathematical Sciences Institute, earned his Ph.D. from ETH Zurich and has held positions at Tel Aviv University, Hebrew University of Jerusalem, and Masaryk University. His research in combinatorics and its connections to linear algebra has implications for probability, geometry, applied mathematics, theoretical computer science, and quantum physics.