In a new video, I do a deep dive with Rishi Sonthalia and Anna Gilbert about their paper on optimization with metric constraints – and their associated code together with my former student Nate Veldt who worked on similar problems with me. Their stuff is super cool and we go into why it’s awesome!

The video - <youtu.be/OBC4FmUui…>

Their paper - <arxiv.org/abs/2005….>

Their code - <github.com/rsonthal/…>

More context – a month or so ago (who can keep track of time – maybe this was September, actually) I sat down with Rishi Sonthalia, my former student Nate Veldt, and Anna Gilbert to understand Rishi and Anna’s latest paper on “Project and Forget Metric Optimization” <arxiv.org/abs/2005….>. For fun, we decided to record this so that I’d be able to look at this again when I wanted to keep working on this. But it turned out so great we figured we’d share it! (After spending too much time editing it, of course…!)

I care about this because it gives a faster way to solve a quadratic or linear program based on a relaxation of the correlation clustering problem. I think it also gives a great place to build future HPC-style work on graphs where there is a problem that takes considerable time and computing effort. The particular bottleneck in the current code is computing an all-pairs-shortest path computation, which is somewhere where there has been a tremendous amount of work that could be used to make this go even faster!