TY - GEN

T1 - On distributed merlin-arthur decision protocols

AU - Fraigniaud, Pierre

AU - Montealegre, Pedro

AU - Oshman, Rotem

AU - Rapaport, Ivan

AU - Todinca, Ioan

N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.

PY - 2019

Y1 - 2019

N2 - In a distributed locally-checkable proof, we are interested in checking the legality of a given network configuration with respect to some Boolean predicate. To do so, the network enlists the help of a prover—a computationally-unbounded oracle that aims at convincing the network that its state is legal, by providing the nodes with certificates that form a distributed proof of legality. The nodes then verify the proof by examining their certificate, their local neighborhood and the certificates of their neighbors. In this paper we examine the power of a randomized form of locally-checkable proof, called distributed Merlin-Arthur protocols, or dMA for short. In a dMA protocol, the prover assigns each node a short certificate, and the nodes then exchange random messages with their neighbors. We show that while there exist problems for which dMA protocols are more efficient than protocols that do not use randomness, for several natural problems, including Leader Election, Diameter, Symmetry, and Counting Distinct Elements, dMA protocols are no more efficient than standard nondeterministic protocols. This is in contrast with Arthur-Merlin (dMA) protocols and Randomized Proof Labeling Schemes (RPLS), which are known to provide improvements in certificate size, at least for some of the aforementioned properties.

AB - In a distributed locally-checkable proof, we are interested in checking the legality of a given network configuration with respect to some Boolean predicate. To do so, the network enlists the help of a prover—a computationally-unbounded oracle that aims at convincing the network that its state is legal, by providing the nodes with certificates that form a distributed proof of legality. The nodes then verify the proof by examining their certificate, their local neighborhood and the certificates of their neighbors. In this paper we examine the power of a randomized form of locally-checkable proof, called distributed Merlin-Arthur protocols, or dMA for short. In a dMA protocol, the prover assigns each node a short certificate, and the nodes then exchange random messages with their neighbors. We show that while there exist problems for which dMA protocols are more efficient than protocols that do not use randomness, for several natural problems, including Leader Election, Diameter, Symmetry, and Counting Distinct Elements, dMA protocols are no more efficient than standard nondeterministic protocols. This is in contrast with Arthur-Merlin (dMA) protocols and Randomized Proof Labeling Schemes (RPLS), which are known to provide improvements in certificate size, at least for some of the aforementioned properties.

KW - Distributed verification

KW - Interactive computation

KW - Interactive proof systems

KW - Nondeterminism

UR - http://www.scopus.com/inward/record.url?scp=85069824108&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-24922-9_16

DO - 10.1007/978-3-030-24922-9_16

M3 - Conference contribution

AN - SCOPUS:85069824108

SN - 9783030249212

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 230

EP - 245

BT - Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, Proceedings

A2 - Censor-Hillel, Keren

A2 - Flammini, Michele

PB - Springer Verlag

T2 - 26th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2019

Y2 - 1 July 2019 through 4 July 2019

ER -