University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

ColloquiumExport this event to calendar

Monday, November 18, 2019 — 4:00 PM EST

Henry Yuen, University of Toronto

"Connes’ Embedding Problem through the lens of complexity theory"

The Connes Embedding Problem (CEP) is a long-standing question in the field of operator algebras, and is known to be equivalent to a number of other conjectures across mathematics. Remarkably, the CEP is also connected to fundamental questions in quantum information theory. In particular, a positive resolution to the CEP implies the existence of an algorithm to approximately compute the optimal winning probability of nonlocal games. This motivates an intriguing complexity-theoretic approach to exploring the CEP: obtaining lower bounds on the complexity of nonlocal games implies limits on the CEP, whereas upper bounds gives evidence towards its positive resolution.

I will give an overview of this fascinating connection between the Connes Embedding Problem, nonlocal games, and computational complexity, and I will discuss some new results about the complexity of nonlocal games (joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright).

MC 5501

S M T W T F S
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2021 (35)
    1. May (1)
    2. April (4)
    3. March (11)
    4. February (9)
    5. January (10)
  2. 2020 (103)
    1. December (10)
    2. November (12)
    3. October (4)
    4. September (3)
    5. August (1)
    6. July (5)
    7. June (1)
    8. May (3)
    9. March (16)
    10. February (26)
    11. January (22)
  3. 2019 (199)
  4. 2018 (212)
  5. 2017 (281)
  6. 2016 (335)
  7. 2015 (211)
  8. 2014 (235)
  9. 2013 (251)
  10. 2012 (135)