论文标题
在分布式交互式证明中共享与私人随机性
Shared vs Private Randomness in Distributed Interactive Proofs
论文作者
论文摘要
在分布式的交互式证明中，图G的节点与一个强大但不可信的供者互动，他们试图在少量的回合中并通过简短消息说服他们满足某些属性。这一系列的相互作用之后是分布式验证阶段，该阶段可以是确定性的或随机的，其中节点与邻居交换消息。 最后一个验证的本质定义了两种类型的交互式协议。我们说，如果验证回合是确定性的，则该协议是Arthur-Merlin类型的。我们说，如果允许节点使用一组新的随机位，则该协议是Merlin-Arthur类型的。 在Kol，Oshman和Saxena [PODC 2018]引入的原始模型中，随机性是私人的，因为每个节点都只能访问单个随机硬币的源。 Crescenzi，Fraigniaud和Paz [Disc 2019]启动了分布式交互模型中共享随机性的影响（所有节点都可以看到硬币折腾的情况）。 在这项工作中，我们通过表明两种形式的随机性的影响取决于我们是考虑了Arthur-Merlin方案还是Merlin-Arthur方案，从而继续进行研究。虽然私人随机性为第一种协议提供了更大的功能，但共享随机性为第二个协议提供了更大的功能。我们的结果还将分布式交互式证明中的共享随机性与分布式验证联系起来，并获得了新的下限。
In distributed interactive proofs, the nodes of a graph G interact with a powerful but untrustable prover who tries to convince them, in a small number of rounds and through short messages, that G satisfies some property. This series of interactions is followed by a phase of distributed verification, which may be either deterministic or randomized, where nodes exchange messages with their neighbors. The nature of this last verification round defines the two types of interactive protocols. We say that the protocol is of Arthur-Merlin type if the verification round is deterministic. We say that the protocol is of Merlin-Arthur type if, in the verification round, the nodes are allowed to use a fresh set of random bits. In the original model introduced by Kol, Oshman, and Saxena [PODC 2018], the randomness was private in the sense that each node had only access to an individual source of random coins. Crescenzi, Fraigniaud, and Paz [DISC 2019] initiated the study of the impact of shared randomness (the situation where the coin tosses are visible to all nodes) in the distributed interactive model. In this work, we continue that research line by showing that the impact of the two forms of randomness is very different depending on whether we are considering Arthur-Merlin protocols or Merlin-Arthur protocols. While private randomness gives more power to the first type of protocols, shared randomness provides more power to the second. Our results also connect shared randomness in distributed interactive proofs with distributed verification, and new lower bounds are obtained.
