Concepedia

Interactive Proof Complexity Classes

Interactive Proof Complexity Classes is a complexity-theoretic classification framework that distinguishes subclasses of problems solvable via interactive protocols between a probabilistic polynomial-time verifier and one or more provers, based on the number of interaction rounds, the amount of randomness, and the computational power of the participants.

26

Publications

955

Citations

43

Authors

31

Institutions

Publications per year

2017–2026

1

Parents

Publications

26

Limits on the power of quantum statistical zero-knowledge

John Watrous · 2003 · 113 citations

, , +16

On the complexity of interactive proofs with bounded communication

Oded Goldreich, Johan Håstad · Information Processing Letters · 1998 · 84 citations

, , +12

On the Hardness of Distinguishing Mixed-State Quantum Computations

Bill Rosgen, John Watrous · 2005 · 71 citations

, , +14

Verifying computations with streaming interactive proofs

Graham Cormode, Justin Thaler, Ke Yi · Proceedings of the VLDB Endowment · 2011 · 63 citations

, , +17

SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE

Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana et al. · 2021 · 62 citations

, , +17

1–5 of 26

Authors

43

  1. JW
    John Watrous

    University of Calgary, Canada

    4 publications · 239 citations

    4

    h-index

  2. JH
    Johan Håstad

    KTH Royal Institute of Technology, Sweden

    4 publications · 175 citations

    4

    h-index

  3. LB
    László Babai

    University of Chicago, United States

    3 publications · 117 citations

    3

    h-index

  4. GC
    Graham Cormode

    AT&T (United States), United States

    2 publications · 73 citations

    2

    h-index

  5. TV
    Thomas Vidick

    California Institute of Technology, United States

    2 publications · 95 citations

    2

    h-index

1–5 of 43

Institutions

31

  1. Massachusetts Institute of Technology

    Cambridge, United States

    5 h-index

    8 publications

    341 citations

  2. University of Calgary

    Calgary, Canada

    3 h-index

    3 publications

    200 citations

  3. KTH Royal Institute of Technology

    Stockholm, Sweden

    3 h-index

    3 publications

    129 citations

  4. Core Competence

    Santa Fe, United States

    2 h-index

    2 publications

    45 citations

  5. University of Waterloo

    Waterloo, Canada

    2 h-index

    2 publications

    63 citations

  6. University of Chicago

    Chicago, United States

    2 h-index

    3 publications

    99 citations

  7. Weizmann Institute of Science

    Rehovot, Israel

    2 h-index

    2 publications

    107 citations

  8. Herzliya Medical Center

    Herzliya, Israel

    1 h-index

    1 publications

    26 citations

1–8 of 31

Venues

  1. Proceedings of the VLDB Endowment

    PVLDB · 1 publications · 63 citations

    1

    h-index

  2. SIAM Journal on Discrete Mathematics

    1 publications · 50 citations

    1

    h-index

  3. International Journal of Foundations of Computer Science

    IJFCS · 1 publications · 11 citations

    1

    h-index

  4. 1

    h-index

  5. ArXiv.org

    Repository · 1 publications · 16 citations

    1

    h-index

1–5