Concepedia

Arthur-merlin Protocols

Arthur-Merlin Protocols is a type of interactive proof system in computational complexity theory where a computationally unbounded prover (Merlin) attempts to convince a probabilistic polynomial-time verifier (Arthur) of the truth of a statement through a sequence of messages, with Arthur’s randomness being public and the protocol’s soundness and completeness relying on the interaction’s prescribed structure.

43

Publications

2.9K

Citations

67

Authors

44

Institutions

Publications per year

2017–2026

1

Variants

Am Protocols

Parents

Publications

43

Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes

László Babai, Shlomo Moran · Journal of Computer and System Sciences · 1988 · 596 citations

, , +16

How to go beyond the black-box simulation barrier

Boaz Barak · 2001 · 486 citations

, , +15

On the Composition of Zero-Knowledge Proof Systems

Oded Goldreich, Hugo Krawczyk · SIAM Journal on Computing · 1996 · 427 citations

, , +17

Quantum Arthur–Merlin games

Chris Marriott, John Watrous · Computational Complexity · 2005 · 253 citations · Full text

, , +16

Does parallel repetition lower the error in computationally sound protocols?

Mihir Bellare, Russell Impagliazzo, Moni Naor · 2002 · 118 citations

, , +15

1–5 of 43

Authors

67

  1. DV
    Dieter van Melkebeek

    University of Wisconsin–Madison, United States

    3 publications · 43 citations

    3

    h-index

  2. PB
    Peter Bro Miltersen

    Aarhus University, Denmark

    3 publications · 175 citations

    3

    h-index

  3. DG
    Dan Gutfreund

    Tel Aviv University, Israel

    3 publications · 87 citations

    3

    h-index

  4. NV
    N. V. Vinodchandran

    University of Nebraska–Lincoln, United States

    2 publications · 147 citations

    2

    h-index

  5. OG
    Oded Goldreich

    Weizmann Institute of Science, Israel

    2 publications · 475 citations

    2

    h-index

1–5 of 67

Institutions

44

  1. Weizmann Institute of Science

    Rehovot, Israel

    6 h-index

    8 publications

    759 citations

  2. University of Wisconsin–Madison

    Madison, United States

    4 h-index

    5 publications

    97 citations

  3. Hebrew University of Jerusalem

    Jerusalem, Israel

    3 h-index

    3 publications

    95 citations

  4. Tel Aviv University

    Tel Aviv, Israel

    2 h-index

    2 publications

    69 citations

  5. IIT@MIT

    Cambridge, United States

    2 h-index

    3 publications

    120 citations

  6. University of Nebraska–Lincoln

    Lincoln, United States

    2 h-index

    2 publications

    147 citations

  7. Universität Ulm

    Ulm, Germany

    2 h-index

    2 publications

    27 citations

  8. University of California San Diego

    San Diego, United States

    2 h-index

    3 publications

    250 citations

1–8 of 44

Venues

  1. Computational Complexity

    CC · 6 publications · 435 citations

    6

    h-index

  2. arXiv (Cornell University)

    Repository · 4 publications · 62 citations

    4

    h-index

  3. SIAM Journal on Computing

    3 publications · 469 citations

    3

    h-index

  4. Quantum Information and Computation

    QIC · 3 publications · 82 citations

    3

    h-index

  5. 2

    h-index

1–5