BARC talk by Taro Spirig

Tuesday, November 5, 2024, Taro Spirig, PhD student at University of Copenhagen in the Department of Mathematics, will give a talk on "Approximation algorithms for noncommutative CSPs".

Abstract:
Constraint satisfaction problems (CSPs) have been widely studied in computer science in the context of NP-hardness and approximation algorithms. For example, the problem of finding optimal k-colourings of graphs, Max-Cut(k), is NP-hard, but it is easy to approximate in the sense that we can efficiently find colourings which are close to the optimal one. We study a noncommutative variant of CSPs (NC-CSPs) that is central in quantum information, where the variables of CSPs are replaced by operators. In this context, even approximating NC-CSPs is known to be much harder than the classical case, in fact it is uncomputably hard. On the other hand, NC-Max-Cut(2) becomes efficiently solvable. Apart from these two facts, not much was previously known about the complexity of NC-CSPs. We introduce a framework for designing approximation algorithms for NC-CSPs based on SDP relaxations. In this talk, we focus on the example of NC-Max-Cut(3) which is known to be undecidable and we present a 0.864-approximation algorithm for this problem. This talk is based on work with Eric Culf and Hamoon Mousavi (arxiv.org/abs/2312.16765).

Bio:
Taro Spirig is a PhD student at the University of Copenhagen in the Department of Mathematics, working at the centre for the Mathematics of Quantum Theory (QMATH) under the supervision of Prof. Laura Mančinska.
Taro has completed a master's in computational science and engineering at Harvard University and a master's in mathematical and theoretical physics at the university of Oxford. He received his bachelor's degree in physics from ETH Zürich.
His main current interests are in theoretical quantum information theory and quantum complexity theory. Taro is particularly interested in non-local games and the power of entanglement. He is helping organizing a seminar on this topic at the University of Copenhagen, more information here.

Host:
Rasmus Pagh