Welcome to Pure Mathematics

Kieran Mastel, University of Waterloo

The complexity of constraint system games with entanglement

Constraint satisfaction problems (CSPs) are a natural class of decision problems where one must decide whether there is an assignment to variables that satisfies a given formula. Schaefer's dichotomy theorem and its extension to all alphabets due to Bulatov and Zhuk, shows that CSP languages are either efficiently decidable or NP-complete. It is possible to extend CSP languages to quantum assignments using the formalism of nonlocal games. The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. As a consequence, general succinctly presented CSPs are RE-complete. We show that a wide range of NP-complete CSPs become RE-complete when the players are allowed entanglement, including all boolean CSPs, such as 3SAT and 3-colouring. This implies that these CSP languages remain undecidable even when not succinctly presented.

Prior work of Grilo, Slofstra, and Yuen shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems. Hence, such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*?

In this work, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems. In particular, it allows us to use a variant of a CSP due to Dwork, Feige, Kilian, Naor, and Safra that gives a classical MIP protocol for 3SAT with perfect zero knowledge.

To prove our results, we develop a toolkit for analyzing the quantum soundness of reductions between constraint system (CS) games, which we expect to be useful more broadly. In this formalism, synchronous strategies for a nonlocal game correspond to tracial states on an algebra. We equip the algebra with a finitely supported weight that allows us to gauge the players' performance in the corresponding game using a weighted sum of squares. The soundness of our reductions hinges on guaranteeing that specific measurements for the players are close to commuting when their strategy performs well. To this end, we construct commutativity gadgets for all boolean CSPs and show that the commutativity gadget for graph 3-colouring due to Ji is sound against entangled provers. We define a broad class of CSPs that have simple commutativity gadgets. We show a variety of relations between the different ways of presenting CSPs as games. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.

QNC 2101

9:30am -12:30pm

Joey Lakerdas-Gayle, University of Waterloo

Effective Algebra 6

We will prove Dobritsa's Theorem following the monograph by Downey and Melnikov.

MC 5417

Larissa Kroell, University of Waterloo

Partial C*-dynamical systems and the ideal structure of partial reduced crossed products

We study C*-algebras stemming from partial C*-dynamical systems. We develop equivariant injective envelopes associated to such systems, which allow us to obtain canonical connections to enveloping actions as well as results on the ideal structure of partial crossed products.

We extend the theory of equivariant injective envelopes pioneered by Hamana in the 1980s to partial C*-dynamical systems. To do so, we introduce the category of generalized unital partial actions by allowing for *-automorphisms acting on families of special hereditary subalgebras. Utilizing properties of injective envelopes and the notion of an injective unitization of partial C*-dynamical systems, we argue that it suffices to consider unital objects in our category. This also allows us to connect our theory to Abadie's notion of enveloping actions leading to a canonical relationship of their G-injective envelopes.

Utilizing properties of injective envelopes, we introduce novel non-triviality conditions for partial *-automorphisms inspired by global C*-dynamics. We contrast this notion with existing conditions in the literature. Lastly, we study a non-commutative generalization of stabilizer subgroups for pseudo-Glimm ideals. In particular, we show that for Glimm ideals in the C*-injective envelope, these stabilizer subgroups are in fact amenable --- a result which is crucial for our main theorems regarding the ideal structure of partial reduced crossed products.

Finally, our main application of the theory of G-injective envelopes is a characterization of the ideal intersection property for partial C*-dynamical systems subject to a cohomological condition as a generalization of the result for global group actions. To state this generalization, we utilize the dynamical conditions introduced previously and generalize the notion of equivariant pseudo-expectations to partial C*-dynamical systems. We also give a sufficient intrinsic condition in terms non-commutative uniformly recurrent partial subsystems utilizing pseudo-Glimm ideals. As a consequence of our results, we obtain a full characterization of the ideal intersection property for partial actions on commutative C*-algebras in terms of freeness of the partial action on the spectrum of the G-injective envelope.

MC5403