Special Seminar: Sándor Kisfaludi-Bak "Conditionally Optimal Geometric Algorithms"

Conditionally Optimal Geometric Algorithms

Sándor Kisfaludi-Bak
Max Planck Institute for Informatics
Homepage

Tuesday, 9 March at 13:00
via Zoom: request the link by email [email protected]
Note! the link will be sent to the CS staff separately every day.

Abstract: An algorithm is conditionally optimal if its running time has a matching lower bound based on some established hypothesis in computational complexity. Nowadays, conditional optimality is a natural goal to aim for in several areas of algorithmic research. In this talk, we focus on geometric algorithms, and give some examples where conditional optimality has been achieved. We will then briefly survey the recent progress on the Euclidean travelling salesman problem (TSP): given n points in low-dimensional Euclidean space, what is the shortest round trip that visits all the points? We will discuss the recent conditionally optimal exact algorithm and the new conditionally optimal approximation scheme for Euclidean TSP, and some related work. In the end, we will highlight some promising research directions in the broad area of geometric algorithms.

Bio: Sándor completed his PhD in the Netherlands at TU Eindhoven in 2019, and his work received the EATCS Distinguished Dissertation Award from the European Association for Theoretical Computer Science. Since 2019 he is a postdoc at the Max Planck Institute for Informatics, working in the Department of Algorithms and Complexity. His primary research interests lie in computational geometry and parameterized algorithms.