Concepedia

Multi-prover Interactive Proofs

Multi-Prover Interactive Proofs is an interactive proof system in which a probabilistic polynomial-time verifier interacts with multiple provers who are computationally unbounded but unable to communicate with one another, thereby enabling stronger verification power through spatially separated cooperation.

26

Publications

2.4K

Citations

41

Authors

28

Institutions

Publications per year

2017–2026

2

Parents

Publications

26

Interactive proofs and the hardness of approximating cliques

Uriel Feige, Shafi Goldwasser, László Lovász et al. · Journal of the ACM · 1996 · 524 citations · Full text

, , +16

Multi-prover interactive proofs: how to remove intractability

Michael Ben-Or, Shafi Goldwasser, Joe Kilian · 1988 · 484 citations

, , +15

Consequences and Limits of Nonlocal Strategies

2004 · 310 citations

, , +16

On the power of multi-prover interactive protocols

Lance Fortnow, John Rompel, Michael Sipser · Theoretical Computer Science · 1994 · 190 citations

, , +7

Consequences and limits of nonlocal strategies

Richard Cleve, Ben Toner, John Watrous · 2004 · 166 citations

, , +16

1–5 of 26

Authors

41

  1. HK
    Hirotada Kobayashi

    National Institute of Informatics, Japan

    5 publications · 267 citations

    5

    h-index

  2. TV
    Thomas Vidick

    California Institute of Technology, United States

    4 publications · 154 citations

    4

    h-index

  3. KM
    Keiji Matsumoto

    National Institute of Informatics, Japan

    4 publications · 240 citations

    4

    h-index

  4. TI
    Tsuyoshi Ito

    The University of Tokyo, Japan

    3 publications · 156 citations

    3

    h-index

  5. JW
    John Watrous

    University of Calgary, Canada

    3 publications · 211 citations

    3

    h-index

1–5 of 41

Institutions

28

  1. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    6 publications

    1.2K citations

  2. National Institute of Informatics

    Tokyo, Japan

    4 h-index

    7 publications

    307 citations

  3. University of California, Berkeley

    Berkeley, United States

    3 h-index

    3 publications

    94 citations

  4. Hebrew University of Jerusalem

    Jerusalem, Israel

    2 h-index

    5 publications

    97 citations

  5. University of Chicago

    Chicago, United States

    2 h-index

    3 publications

    99 citations

  6. Tel Aviv University

    Tel Aviv, Israel

    2 h-index

    2 publications

    67 citations

  7. McGill University

    Montreal, Canada

    2 h-index

    2 publications

    100 citations

  8. California Institute of Technology

    Pasadena, United States

    2 h-index

    2 publications

    197 citations

1–8 of 28

Venues

  1. ArXiv.org

    Repository · 2 publications · 32 citations

    2

    h-index

  2. Journal of Computer and System Sciences

    1 publications · 100 citations

    1

    h-index

  3. Structure in Complexity Theory Annual Conference

    Conference · 1 publications · 16 citations

    1

    h-index

  4. Theoretical Computer Science

    1 publications · 190 citations

    1

    h-index

  5. SIAM Journal on Computing

    1 publications · 45 citations

    1

    h-index

1–5