Concepedia

Merlin-arthur Protocols

Merlin-Arthur Protocols is a type of interactive proof system in computational complexity theory where a powerful but untrusted prover (Merlin) sends a single message to a probabilistic polynomial-time verifier (Arthur), who then decides whether to accept or reject based on that message and his own random coins.

43

Publications

3.1K

Citations

66

Authors

59

Institutions

Publications per year

2017–2026

3

Variants

Ma

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

Quantum Computational Complexity of the<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>N</mml:mi></mml:math>-Representability Problem: QMA Complete

Yi-Kai Liu, Matthias Christandl, Frank Verstraete · Physical Review Letters · 2007 · 217 citations · Full text

, , +17

1–5 of 43

Authors

66

  1. JT
    Justin Thaler

    Harvard University, United States

    3 publications · 43 citations

    3

    h-index

  2. AW
    Aram W. Harrow

    Massachusetts Institute of Technology, United States

    3 publications · 157 citations

    3

    h-index

  3. DG
    Dan Gutfreund

    Tel Aviv University, Israel

    3 publications · 87 citations

    3

    h-index

  4. AM
    Ashley Montanaro

    University of Bristol, United Kingdom

    3 publications · 157 citations

    3

    h-index

  5. SA
    Scott Aaronson

    Massachusetts Institute of Technology, United States

    2 publications · 39 citations

    2

    h-index

1–5 of 66

Institutions

59

  1. Weizmann Institute of Science

    Rehovot, Israel

    6 h-index

    8 publications

    759 citations

  2. University of California San Diego

    San Diego, United States

    3 h-index

    4 publications

    473 citations

  3. University of Cambridge

    Cambridge, United Kingdom

    3 h-index

    3 publications

    360 citations

  4. California Institute of Technology

    Pasadena, United States

    2 h-index

    2 publications

    244 citations

  5. Universidade Federal de Minas Gerais

    Belo Horizonte, Brazil

    2 h-index

    2 publications

    71 citations

  6. University of Washington

    Seattle, United States

    2 h-index

    2 publications

    143 citations

  7. Technion – Israel Institute of Technology

    Haifa, Israel

    2 h-index

    3 publications

    626 citations

  8. Gunma University

    Maebashi, Japan

    2 h-index

    2 publications

    43 citations

1–8 of 59

Venues

  1. arXiv (Cornell University)

    Repository · 4 publications · 62 citations

    4

    h-index

  2. Computational Complexity

    CC · 4 publications · 345 citations

    4

    h-index

  3. Quantum Information and Computation

    QIC · 3 publications · 82 citations

    3

    h-index

  4. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 2 publications · 38 citations

    2

    h-index

  5. 2

    h-index

1–5