Talks and Abstracts (tentative)

Laura Mančinska: Quantum reductions for nonlocal games

Gap-preserving reductions are central to classical complexity theory, but their quantum counterparts—especially in the context of multiprover interactive proofs with entangled provers—pose new challenges. In this talk I will discuss a framework for such reductions in the MIP* setting and use it to show that the gapped promise problem for independent set games is MIP*-complete. These games, with constant question size, can be undecidable in the quantum case yet polynomial-time solvable classically. A key technical tool is a new stability theorem that converts almost projective measurements into exact ones.

This talk is baed on a joint work with Pieter Spaas, Taro Spirig, and Matthijs Vernooij.

Anand Natarajan: Succinct arguments for QMA from standard assumptions, without quantum PCPs

In this talk, I will explain how to construct succinct classical interactive arguments for QMA, using only standard cryptographic assumptions (implied by LWE). Our approach builds on Kalai, Lombardi, Vaikuntanathan’s “compiler” to convert a two-prover interactive proof in the MIP* model into a one-prover interactive argument, and achieves succinctness by combining ideas from the MIP* literature with post-quantum succinct arguments of knowledge. Perhaps unexpectedly, our construction does not yield any form of quantum PCP—neither a “Hamiltonian” PCP nor a “games” PCP—in contrast to the situation in the classical world, where PCPs appear to be inherent to succinct arguments for NP.

Based on joint work with Tony Metger and Tina Zhang (2404.19754)