We are home to 30 faculty, four staff, approximately 60 graduate students, several research visitors, and numerous undergraduate students. We offer exciting and challenging programs leading to BMath, MMath and PhD degrees. We nurture a very active research environment and are intensely devoted to both ground-breaking research and excellent teaching.
News
53rd annual COSY conference a success
More than 100 researchers and students from across Canada and around the world attended the 53rd annual Canadian Operator Algebras Symposium (COSY), which took place from May 26-30 at the University of Waterloo.
Pure Math Department celebrates undergraduate achievement at awards tea
On March 24, the department of Pure Mathematics held its annual Undergraduate Awards Tea, an event that celebrates the accomplishments of its remarkable undergraduate students.
Two Pure Math professors win Outstanding Performance Awards
The awards are given each year to faculty members across the University of Waterloo who demonstrate excellence in teaching and research.
Events
Differential Geometry Working Seminar
Paul Cusson, University of Waterloo
Vector bundles over a complex torus
We will cover basic results about the complex geometry of a complex torus X, followed by a discussion of holomorphic vector bundles over X. An immediate result due to Hodge theory is the existence of complex bundles that don't admit holomorphic structures when the complex dimension of X is at least 2. We will thus focus on bundles whose Chern classes lie in the diagonal of the Hodge diamond and ask which ones can be holomorphic.
MC 5403
Differential Geometry Working Seminar
Kaleb Ruscitti, University of Waterloo
Embedding a family of moduli spaces of SL(2,C) bundles into projective spaces
The moduli space of polystable degree-0 SL(2,C) bundles on a compact connected Riemann surface of genus g>=2 is a Kähler manifold, and an open subset of the moduli space of semi-stable bundles, which is a projective variety of dimension 3g-3. Biswas and Hurtubise constructed a toric degeneration of this moduli space, meaning a family of moduli spaces over C whose fiber over 0 is a toric variety. The toric variety has a moduli interpretation as a space of framed parabolic bundles.
In this talk, I will describe the family and then describe how one can embed the entire family into P^N x C. This is the key step in a current project I am working on, about relating different geometric quantizations of the moduli space of SL(2,C) bundles.
MC 5403
PhD Thesis Defence
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