On the power of many one-bit provers
2013 (English)In: ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, New York: Association for Computing Machinery (ACM), 2013, 215-220 p.Conference paper (Refereed)
We study the class of languages, denoted by MIP[k, 1-∈, s], which have k-prover games where each prover just sends a single bit, with completeness 1-∈ and soundness error s. For the case that k=1 (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson (Computational Complexity'02) demonstrate that SZK exactly characterizes languages having 1-bit proof systems with "non-trivial" soundness (i.e., 1/2 < s ≤ 1-2∈). We demonstrate that for the case that k ≥ 2, 1-bit k-prover games exhibit a significantly richer structure: •(Folklore) When s ≤ 1/2 k - ∈, MIP[k, 1-∈, s] = BPP; • When 1/2k + ∈ ≤ s < 2/2k -∈, MIP[k, 1-∈, s] = SZK; • When s ≥ 2/2k + ∈, AM ⊆ MIP[k, 1-∈, s]; • For s ≤ 0.62 k/2k and sufficiently large k, MIP[k, 1-∈, s] ⊆ EXP; • For s ≥ 2k/2k, MIP[k, 1, 1-∈, s] = NEXP. As such, 1-bit k-prover games yield a natural "quantitative" approach to relating complexity classes such as BPP, SZK, AM, EXP, and NEXP. We leave open the question of whether a more fine-grained hierarchy (between AM and NEXP) can be established for the case when s ≥ 2/2k + ∈.
Place, publisher, year, edition, pages
New York: Association for Computing Machinery (ACM), 2013. 215-220 p.
laconic provers, multi-prover interactive proofs, Complexity class, Interactive proofs
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-136054DOI: 10.1145/2422436.2422461ScopusID: 2-s2.0-84873402892ISBN: 978-145031859-4OAI: oai:DiVA.org:kth-136054DiVA: diva2:670523
2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013; Berkeley, CA; United States; 9 January 2013 through 12 January 2013
QC 201312032013-12-032013-12-032013-12-03Bibliographically approved