BEGIN:VCALENDAR PRODID:-//AddEvent Inc//AddEvent.com v1.7//EN VERSION:2.0 BEGIN:VTIMEZONE TZID:America/New_York BEGIN:STANDARD DTSTART:20261101T010000 RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:EST END:STANDARD BEGIN:DAYLIGHT DTSTART:20260308T030000 RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:EDT END:DAYLIGHT END:VTIMEZONE BEGIN:VEVENT DESCRIPTION:A Relativizing MIP for BQP\n\nÁgi VillΓ‘nyi | MIT\n\nComplexity class containments involving interactive proof classes are famously nonrelativizing: although 𝖨𝖯=𝖯𝖲𝖯𝖠𝖒𝖀\, Fortnow and Sipser showed that that there exists an oracle relative to which π–Όπ—ˆπ–­π–―βŠˆπ–¨π–―. In contrast\, the question of whether the containment π–‘π–°π–―βŠ†π–¨π–― is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment π–‘π–°π–―βŠ†π–¬π–¨π–― holds with respect to any classical oracle. We obtain this result by constructing\, for any classical oracle O\, a 𝖯𝖒𝖯 proof system for 𝖑𝖰𝖯O where the verifier makes polynomially many classical queries to an exponentially-long proof\, and to the oracle O. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph\, and serves as a complement to the "exponential PCP" constructed by Aharonov\, Arad\, and Vidick\, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency\, and hope that progress towards an 𝖨𝖯 for 𝖑𝖰𝖯 in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world\, which is a longstanding open problem in quantum complexity theory. X-ALT-DESC;FMTTYPE=text/html:A Relativizing MIP for BQP
Ági VillÑnyi | MIT
Complexity class containments involving interactive proof classes are famously nonrelativizing: although 𝖨𝖯=𝖯𝖲𝖯𝖠𝖒𝖀, Fortnow and Sipser showed that that there exists an oracle relative to which π–Όπ—ˆπ–­π–―βŠˆπ–¨π–―. In contrast, the question of whether the containment π–‘π–°π–―βŠ†π–¨π–― is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment π–‘π–°π–―βŠ†π–¬π–¨π–― holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle O, a 𝖯𝖒𝖯 proof system for 𝖑𝖰𝖯O where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle O. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an 𝖨𝖯 for 𝖑𝖰𝖯 in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory. UID:9ebbc17b9f3d42779785adcf2346c558addeventcom SUMMARY:IQC Math and CS seminar featuring Ági VillΓ‘nyi DTSTART;TZID=America/New_York:20261008T130000 DTEND;TZID=America/New_York:20261008T140000 DTSTAMP:20260911T103407Z TRANSP:OPAQUE STATUS:CONFIRMED SEQUENCE:0 LOCATION:QNC 1201 X-MICROSOFT-CDO-BUSYSTATUS:BUSY BEGIN:VALARM TRIGGER:-PT30M ACTION:DISPLAY DESCRIPTION:Reminder END:VALARM END:VEVENT END:VCALENDAR