Eric Culf, Department of Applied Mathematics, University of Waterloo
"Approximation algorithms for noncommutative constraint satisfaction problems"
Constraint satisfaction problems (CSPs) are an important topic of investigation in computer science. 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 it is possible to find a colouring that satisfies a large fraction of the constraints of an optimal one. We study a noncommutative variant of CSPs that is central in quantum information, where the variables are replaced by operators. In this context, even approximating general CSPs is known to be much harder than the classical case, in fact uncomputably hard. Nevertheless, Max-Cut(2) becomes efficiently solvable. We introduce a framework for designing approximation algorithms for noncommutative CSPs, which allows us to find classes of CSPs that are efficiently approximable but not efficiently solvable. To determine the quality of our approximation algorithm, we make use of results from free probability to characterise a distribution arising from random matrices. This talk is based on work with Hamoon Mousavi and Taro Spirig (arxiv.org/abs/2312.16765).
This seminar will be held both online and in person:
- Room: MC 5479
- Zoom link: https://uwaterloo.zoom.us/j/94186354814?pwd=NGpLM3B4eWNZckd1aTROcmRreW96QT09