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:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69e468024958f
DTSTART;TZID=America/Toronto:20240430T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240430T160000
URL:https://uwaterloo.ca/institute-for-quantum-computing/events/two-prover-
 perfect-zero-knowledge-mip
LOCATION:QNC - Quantum Nano Centre 200 University Avenue West 1201 Waterloo
  ON N2L 3G1 Canada
SUMMARY:Two Prover Perfect Zero Knowledge for MIP*
CLASS:PUBLIC
DESCRIPTION:CS/MATH SEMINAR - KIERAN MASTEL FROM IQC ZOOM + IN PERSON\n\nQu
 antum-Nano Centre\, 200 University Ave West\, Room QNC 1201 Waterloo\,\nON
  CA N2L 3G1\n\nThe recent MIP*=RE theorem of Ji\, Natarajan\, Vidick\, Wri
 ght\, and Yuen\nshows that the complexity class MIP* of multiprover proof 
 systems with\nentangled provers contains all recursively enumerable langua
 ges. In\nprior work Grilo\, Slofstra\, and Yuen showed (via a technique ca
 lled\nsimulatable codes) that every language in MIP* has a perfect zero\nk
 nowledge (PZK) MIP* protocol.  The MIP*=RE theorem uses two-prover\none-r
 ound proof systems\, and hence such systems are complete for MIP*.\nHoweve
 r\, the construction in Grilo\, Slofstra\, and Yuen uses six\nprovers\, an
 d there is no obvious way to get perfect zero knowledge\nwith two provers 
 via simulatable codes. This leads to a natural\nquestion: are there two-pr
 over PZK-MIP* protocols for all of MIP*?\n\nIn this talk we answer the que
 stion in the affirmative. For the proof\,\nwe use a new method based on a 
 key consequence of the MIP*=RE theorem\,\nwhich is that every MIP* protoco
 l can be turned into a family of\nboolean constraint system (BCS) nonlocal
  games. This makes it possible\nto work with MIP* protocols as boolean con
 straint systems\, and in\nparticular allows us to use a variant of a const
 ruction due to Dwork\,\nFeige\, Kilian\, Naor\, and Safra which gives a cl
 assical MIP protocol\nfor 3SAT with perfect zero knowledge. To show quantu
 m soundness of\nthis classical construction\, we develop a toolkit for ana
 lyzing\nquantum soundness of reductions between BCS games\, which we expec
 t to\nbe useful more broadly. This talk is based on joint work with Willia
 m\nSlofstra
DTSTAMP:20260419T052834Z
END:VEVENT
END:VCALENDAR