AM with Multiple Merlins
We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detai...
Main Authors: | Aaronson, Scott, Impagliazzo, Russell, Moshkovitz Aaronson, Dana Hadar |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
Format: | Article |
Language: | en_US |
Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
Online Access: | http://hdl.handle.net/1721.1/91565 https://orcid.org/0000-0002-5157-8086 https://orcid.org/0000-0003-1333-4045 |
Similar Items
-
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
by: Moshkovitz Aaronson, Dana Hadar
Published: (2014) -
Parallel Repetition From Fortification
by: Moshkovitz Aaronson, Dana Hadar
Published: (2014) -
Improved Approximation Algorithms for Projection Games
by: Manurangsi, Pasin, et al.
Published: (2014) -
NP-Hardness of Approximately Solving Linear Equations Over Reals
by: Khot, Subhash, et al.
Published: (2011) -
Improved Approximation Algorithms for Projection Games
by: Manurangsi, Pasin, et al.
Published: (2017)