University COVID-19 update

 Visit our Coronavirus Information website for more information.

Spatial Isolation Implies Unconditional Zero Knowledge, Even With EntanglementExport this event to calendar

Thursday, August 9, 2018 — 12:00 PM EDT

Nick Spooner, University of Southern California, Berkeley

Understanding the computational power of multi-prover interactive proofs where the provers may share entanglement -- the complexity class MIP* -- is a central question in quantum computation. In 2012, Ito and Vidick showed that this model is at least as powerful as MIP, i.e. NEXP is contained in MIP*. The original motivation for the introduction of multi-prover interactive proofs, however, was studying unconditional zero knowledge: while single-prover interactive proofs with unconditional zero knowledge are limited to the complexity class SZK, which is not believed to contain NP, with non-communicating provers unconditional zero knowledge is 'for free': ZK-MIP = NEXP. A natural question, then, is: what is the power of ZK-MIP*? This is not immediately clear from the other results, because the techniques used to obtain them seem to be incompatible. In this work, we show that ZK-MIP* contains NEXP, developing new algebraic tools for zero knowledge which are compatible with the Ito-Vidick framework.

Location 
QNC - Quantum Nano Centre
1501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
  1. 2020 (15)
    1. June (4)
    2. April (1)
    3. March (3)
    4. February (5)
    5. January (2)
  2. 2019 (139)
    1. December (7)
    2. November (10)
    3. October (7)
    4. September (5)
    5. August (10)
    6. July (16)
    7. June (13)
    8. May (15)
    9. April (15)
    10. March (11)
    11. February (20)
    12. January (12)
  3. 2018 (144)
  4. 2017 (131)
  5. 2016 (88)
  6. 2015 (82)
  7. 2014 (94)
  8. 2013 (91)
  9. 2012 (122)
  10. 2011 (117)
  11. 2010 (41)
  12. 2009 (4)
  13. 2008 (1)
  14. 2005 (1)
  15. 2004 (3)