A Tale of Turing Machines, Quantum-Entangled Particles, and Operator Algebras

Explore the convergence of computational complexity theory, quantum information, and operator algebras in this Richard M. Karp Distinguished Lecture. Delve into the groundbreaking "MIP* = RE" result, which resolves long-standing problems across multiple fields, including the 44-year-old Connes' Embedding Problem. Trace the evolution of ideas from the 1930s, covering Turing's universal computing machine, quantum entanglement, and von Neumann's operator theory, to cutting-edge developments in theoretical computer science and quantum computing. Gain insights into nonlocal games, interactive proofs, probabilistic checking, and the complexity of entanglement. Suitable for a general scientific audience, this talk requires no specialized background in complexity theory, quantum physics, or operator algebras.

Intro
Theory of Computing
The 1930s
The EPR paradox (1935)
A nonlocal game
The genesis of operator algebras
A zoo of algebras
A mysterious animal
A universal machine and unsolvable problem
Verifying vs finding proofs
The proofs revolution
Verifying proofs interactively
The power of interactivity
Probabilistic checking of proofs
Interactive proofs and entanglement
The complexity of entanglement
An unexpected connection
A candidate algorithm
The proof (from a thousand miles away)
The many facets of MIP* = RE
A Frequently Asked Question
A parable