Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. Although the problem has been the subject of intense algorithmic interest, until recently it was open whether Wasserstein barycenters can be computed in polynomial time. We resolve this question by proving NP-hardness in high dimension and providing a polynomial-time algorithm in fixed dimension. Our proof makes use of a new, general approach to solving multi-marginal optimal transport problems. Joint work with Jason Altschuler.
The seminar will be held over Zoom. Register in advance for this meeting using the following link: https://utoronto.zoom.us/meeting/register/tJcqf-Cqrj4oH9X0X4db3kOgnEhUVGy5AUwe After registering, you will receive a confirmation email containing information about joining the meeting.