Live Stream link:

https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=15e66f0d-59f4-4ae3-b735-ac56011f4988

Title:

Three Tales on Clustering: From theory to practice

Abstract

In the first part of the talk, we will discuss how ideas from theoretical computer science are used in the real-world and how we can bridge the gap between theory and practice. Particularly, we will examine the area of beyond-worst-case analysis (BWCA), which studies how algorithms work in real-life (rather than in the worst case). Then, I will offer you my vision for "developer friendly algorithms" - algorithms that not only work well in practice but also are fast and easy to implement.

In the second part of the talk, I will tell you about my favorite clustering problems and give an overview of my recent results in this area. We will consider several very popular clustering algorithms (such as k-means++) and discuss how well they work both in theory and in practice.

Biography

Konstantin Makarychev is an Associate Professor at the CS Department of Northwestern University. He is interested in designing efficient algorithms for computationally hard problems. The aim of his research is to introduce new core techniques and design general principles for developing and analyzing algorithms that work in theory and practice. Kostya's research interests include approximation algorithms, beyond worst-case analysis, and applications of high-dimension geometry to computer science. Before joining Northwestern, he was a researcher at Microsoft and IBM Research Labs. He obtained a PhD in Computer Science from Princeton University in 2007.