BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20250309T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69f659a5a0cb3
DTSTART;TZID=America/Toronto:20250722T093000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20250722T123000
URL:https://uwaterloo.ca/pure-mathematics/events/phd-thesis-defence-36
SUMMARY:PhD Thesis Defence
CLASS:PUBLIC
DESCRIPTION:KIERAN MASTEL\, UNIVERSITY OF WATERLOO\n\n_The complexity of co
 nstraint system games with entanglement_\n\nConstraint satisfaction proble
 ms (CSPs) are a natural class of\ndecision problems where one must decide 
 whether there is an assignment\nto variables that satisfies a given formul
 a. Schaefer's dichotomy\ntheorem and its extension to all alphabets due to
  Bulatov and Zhuk\,\nshows that CSP languages are either efficiently decid
 able or\nNP-complete. It is possible to extend CSP languages to quantum\na
 ssignments using the formalism of nonlocal games. The recent MIP*=RE\ntheo
 rem of Ji\, Natarajan\, Vidick\, Wright\, and Yuen shows that the\ncomplex
 ity class MIP* of multiprover proof systems with entangled\nprovers contai
 ns all recursively enumerable languages. As a\nconsequence\, general succi
 nctly presented CSPs are RE-complete. We\nshow that a wide range of NP-com
 plete CSPs become RE-complete when the\nplayers are allowed entanglement\,
  including all boolean CSPs\, such as\n3SAT and 3-colouring. This implies 
 that these CSP languages remain\nundecidable even when not succinctly pres
 ented.\n\nPrior work of Grilo\, Slofstra\, and Yuen shows (via a technique
  called\nsimulatable codes) that every language in MIP* has a perfect zero
 \nknowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover\none-
 round proof systems. Hence\, such systems are complete for MIP*.\nHowever\
 , the construction in Grilo\, Slofstra\, and Yuen uses six\nprovers\, and 
 there is no obvious way to get perfect zero knowledge\nwith two provers vi
 a simulatable codes. This leads to a natural\nquestion: are there two-prov
 er PZK-MIP* protocols for all of MIP*? \n\nIn this work\, we show that eve
 ry language in MIP* has a two-prover\none-round PZK-MIP* protocol\, answer
 ing the question in the\naffirmative. For the proof\, we use a new method 
 based on a key\nconsequence of the MIP*=RE theorem\, which is that every M
 IP* protocol\ncan be turned into a family of boolean constraint system (BC
 S)\nnonlocal games. This makes it possible to work with MIP* protocols as\
 nboolean constraint systems. In particular\, it allows us to use a\nvarian
 t of a CSP due to Dwork\, Feige\, Kilian\, Naor\, and Safra that\ngives a 
 classical MIP protocol for 3SAT with perfect zero knowledge.\n\nTo prove o
 ur results\, we develop a toolkit for analyzing the quantum\nsoundness of 
 reductions between constraint system (CS) games\, which we\nexpect to be u
 seful more broadly. In this formalism\, synchronous\nstrategies for a nonl
 ocal game correspond to tracial states on an\nalgebra. We equip the algebr
 a with a finitely supported weight that\nallows us to gauge the players' p
 erformance in the corresponding game\nusing a weighted sum of squares. The
  soundness of our reductions\nhinges on guaranteeing that specific measure
 ments for the players are\nclose to commuting when their strategy performs
  well. To this end\, we\nconstruct commutativity gadgets for all boolean C
 SPs and show that the\ncommutativity gadget for graph 3-colouring due to J
 i is sound against\nentangled provers. We define a broad class of CSPs tha
 t have simple\ncommutativity gadgets. We show a variety of relations betwe
 en the\ndifferent ways of presenting CSPs as games. This toolkit also appl
 ies\nto commuting operator strategies\, and our argument shows that every\
 nlanguage with a commuting operator BCS protocol has a two prover PZK\ncom
 muting operator protocol.\n\nQNC 2101 \n\n9:30am -12:30pm
DTSTAMP:20260502T200805Z
END:VEVENT
END:VCALENDAR