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.

computer science theoryMathematics

Audience: researchers in the topic

University of Birmingham theoretical computer science seminar

Series comments: Meeting ID: 818 7333 5084 ~ Password: 217