The layer complexity of Arthur-Merlin-like communication

DOI10.4086/TOC.2021.V017A008MaRDI QIDQ5158502zbMATH OpenOpenAlexFDO

Authors Dmitry Gavinsky

Publication date 25 October 2021

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1811.04010

zbMATH Keywords

complexity classescommunication complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of computing (68Qxx)

Recommendations

• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Zero-information protocols and unambiguity in Arthur-Merlin communication (extended abtract)
• Arthur-Merlin games in Boolean decision trees
• scientific article; zbMATH DE number 1335880
• Relativized Arthur-Merlin versus Merlin-Arthur games

Cites work

• Algebrization: a new barrier in complexity theory
• Communication Complexity
• Concentration bounds for unigram language models
• Error-bounded probabilistic computations between MA and AM
• Lower Bounds on Information Transfer in Distributed Computations
• Non-deterministic communication complexity with few witnesses
• On the hardness of approximate and exact (bichromatic) maximum inner product
• On the power of statistical zero knowledge
• Rectangles are nonnegative juntas
• The landscape of communication complexity classes
• Zero-information protocols and unambiguity in Arthur-Merlin communication

Cited in

(2)

• Zero-information protocols and unambiguity in Arthur-Merlin communication
• New lower bounds in Merlin-Arthur communication and graph streaming verification

This page was built for publication: The layer complexity of Arthur-Merlin-like communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5158502)