Location
MC 6460
Candidate
Eric Culf | Applied Mathematics, University of Waterloo
Title
The Complexity of Entangled Constraint Satisfaction Problems
Abstract
Due to entanglement, a strong form of correlation arising from quantum mechanics, the expressive power of correlation scenarios, such as nonlocal games, is much increased with quantum provers. However, it is poorly understood in which scenarios this additional complexity arises. For example, the value of an XOR nonlocal game is actually much easier to find quantumly than classically. In this project, I aim to improve the understanding of which classes of nonlocal games exhibit high complexity, and for which completeness-soundness gaps.
The proposed project builds on past and ongoing work. In work with Hamoon Mousavi and Taro Spirig, we developed approximation algorithms for nonlocal games, that show that there are games of intermediate complexity that are easy to approximate while being hard to solve exactly. In ongoing work with Kieran Mastel, we aim to show that many natural classes of games arising from constraint satisfaction problems are uncomputably difficult to approximate with some constant gap.