Events

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

Robert Harris, University of Waterloo

Exotic constructions on covers branched over hyperplane arrangements

As a consequence of embedded surfaces and codimension two submanifolds coinciding in dimension four, many of the tools that are used in higher dimensions fail or are underwhelming when applied to 4-manifolds. For this reason, the development and advancement of techniques that are applicable to 4-manifolds are of particular interest and importance to low dimensional topologists. The general techniques of interest are those that either construct a 4-manifold in a novel way or those that provide ample control over the geometric data of the resulting 4-manifold.

In this talk, I will discuss my thesis, in which we investigate ways to construct 4-manifolds with positive signature. We also describe a construction that can guarantee the existence of algebraically interesting embedded symplectic submanifolds.

Specifically, we discuss how the combinatorial data of line arrangements and the algebraic data of their complements in rational complex surfaces can be utilized to construct symplectic 4-manifolds with arbitrarily large signatures through the method of branched coverings. In general, we not only show that these line arrangements can be used to provide asymptotic bounds for the existence of symplectic 4-manifolds but we also show that for any line arrangement, there exists symplectic branched covers with sufficiently nice geometric and topological properties. Namely, we show they contain embedded symplectic Riemann surfaces which carry their fundamental group.

Online presentation: contact r26harri@uwaterloo.ca for details on how to attend

Samantha Nadia Pater, Cuiwen Zhu and Hanwu Zhou

The Hasse Principle for Diagonal Forms via the Circle Method

The Hasse principle predicts that a Diophantine equation should have a rational solution whenever it has solutions in reals and p-adics for all primes p. For diagonal forms, this principle can be analyzed via the Hardy–Littlewood circle method. In this talk, we examine how the major and minor arc contributions are handled to establish asymptotic formulas for the number of integral solutions. Moreover, we would present a sketch of Jorg Brudern and Trevor D. Wooley's proof of the Hasse principle for pairs of diagonal cubic forms in thirteen or more variables.

MC 5417

Amanda Petcu, University of Waterloo

Cohomogeneity one solitons of the hypersymplectic flow

Given a hypersymplectic manifold X^4, one can give a flow of hypersymplectic structures. In this talk, we let X^4 be R^4 with an SO(4) action, and the hypersymplectic triple depend on three different functions h_k that depend solely on the radial coordinate. We will examine how the triple evolves under the hypersymplectic flow and given this initial structure, determine all possible solitons of the flow.

MC 5403

Anton Iliashenko, Beijing Institute of Mathematical Sciences and Applications

Hyperbolicity and Schwarz Lemmas in Calibrated Geometry

We will define two new notions of hyperbolicity for a general Riemannian manifold equipped with a calibration, which generalize the notions of Kobayashi and Brody hyperbolicity from complex geometry. For this we introduce a decreasing Finsler pseudo-metric that specializes to the Kobayashi-Royden pseudo-metric in the Kahler case; and derive the generalization of the classical Schwarz Lemma but for Smith immersions. We will talk about how these notions of hyperbolicity relate to one another and will see some examples. This is joint work with Kyle Broder and Jesse Madnick.

MC 5417

Alex Pawelko, University of Waterloo

Gerbes of Coassociative Submanifolds and the first Chern class

We will define (bundle) gerbes, a generalization of principal S^1-bundles, and define connections on gerbes, whose corresponding forms over a trivialization are 2-forms and whose curvatures are 3-forms. Then, we will build a gerbe from coassociative submanifolds of a G_2 manifold, and study its analogue of the first Chern class, an integral cohomology class in degree 3.

MC 5403

Xuemiao Chen, University of Waterloo

Space of lines-II

I will continue to talk about some related constructions on the space of oriented lines in the three dimensional Euclidean space.

MC 5403

Noah Slavitch, University of Waterloo

Generic Absoluteness in Set Theory

We give an overview of the study of generic absoluteness for V in set theory, including a discussion of projective absoluteness and Sealing.

MC 5403