Extremal Combinatorics Meets Algorithms and Data Structures

Abstract: This talk explores a rich interplay between extremal combinatorics and the analysis of algorithms and data structures. In the first part of the talk, I will explain how classical Ramsey theory

tightly captures a fundamental question in approximation algorithms and how the LP rounding perspectives (techniques that are central in approximation algorithms) led to breaking a 6-decade-old extremal bound on rectangle coloring. In the second part, I will discuss the role of extremal combinatorics in the context of sorting and binary search trees (in particular, the long-standing dynamic optimality conjecture). In both scenarios, such interplay has been crucial in making progress and highlights the two-way dialogue between the two fields.

Please note that there is a gap in the sound around the 30:28 minute mark, apologies for this.