BARC talk by Parinya Chalermsook

Wednesday, 20 October 2021, Parinya Chalermsook, Assistant Professor at Aalto Unioversity in Finland, will give a talk on "Algorithms, Extremal Combinatorics, and Rectangles ".

Algorithms, Extremal Combinatorics, and Rectangles 

In this talk, Parinya will start with a broad perspective on the interplay between extremal combinatorics and algorithms (focusing on approximation algorithms). After that, he will present his recent result in this context (joint with Bartosz Walczak). They show that any rectangle graph admits an O(q log q) coloring where q is the clique number of the input graph. This is the first asymptotic improvement over the six-decade-old bound obtained by Asplund and Grünbaum in 1960.

Parinya Chalermsook studies the interplay between algorithms and optimization. He is currently an assistant professor at Aalto University (Finland). He got his Ph.D. from the University of Chicago under the supervision of Julia Chuzhoy and Janos Simon in 2012. He worked as a postdoc and (later) a senior researcher at Max Planck Institute for Informatics. Parinya has worked on computational problems arising from a wide range of domains, such as data structures, algorithmic game theory, networking, and computational geometry. He has been awarded a Simons-Berkeley Research Fellowship (2016) and an ERC Starting Grant (2017).