检索结果-内蒙古大学图书馆

Shared Versus Private Randomness in distributed interactive proofs

ALGORITHMICA 2025年第3期87卷 377-404页

作者： Montealegre, Pedro Ramirez-Romero, Diego Rapaport, Ivan Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile Milenium Nucleus Social Data Sci SODAS Santiago Chile Univ Chile Dept Ingn Matemat Santiago Chile Univ Chile CNRS UMI 2807 DIMCMM Santiago Chile

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 rounds 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. We also show that there exists at most an exponential gap between the certificate size in distributed interactive proofs with respect to distributed verification protocols without any randomness.

关键词： distributed interactive proofs distributed verification Shared randomness Private randomness

来源：评论

学校读者我要写书评

暂无评论

distributed interactive proofs for the Recognition of Some Geometric Intersection Graph Classes 1

引用

29th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Jauregui, Benjamin Montealegre, Pedro Rapaport, Ivan Univ Chile Dept Ingn Matemat Santiago Chile Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile Univ Chile CNRS DIM CMM UMI 2807 Santiago Chile

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

A graph G = (V, E) is a geometric intersection graph if every node v is an element of V is identified with a geometric object of some particular type, and two nodes are adjacent if the corresponding objects intersect. Geometric intersection graph classes have been studied from both the theoretical and practical point of view. On the one hand, many hard problems can be efficiently solved or approximated when the input graph is restricted to a geometric intersection class of graphs. On the other hand, these graphs appear naturally in many applications such as sensor networks, scheduling problems, and others. Recently, in the context of distributed certification and distributed interactive proofs, the recognition of graph classes has started to be intensively studied. Different results related to the recognition of trees, bipartite graphs, bounded diameter graphs, triangle-free graphs, planar graphs, bounded genus graphs, H-minor free graphs, etc., have been obtained. The goal of the present work is to design efficient distributed protocols for the recognition of relevant geometric intersection graph classes, namely permutation graphs, trapezoid graphs, circle graphs and polygoncircle graphs. More precisely, for the two first classes we give proof labeling schemes recognizing them with logarithmic-sized certificates. For the other two classes, we give three-round distributed interactive protocols that use messages and certificates of size O(log n). Finally, we provide logarithmic lower-bounds on the size of the certificates on the proof labeling schemes for the recognition of any of the aforementioned geometric intersection graph classes.

关键词： distributed decision Proof-labeling scheme distributed interactive proofs Intersection Graph Classes

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: New distributed interactive proofs for Planarity: A Matter of Left and Right 25

Brief Announcement: New Distributed Interactive Proofs for P...

引用

Proceedings of the ACM Symposium on Principles of distributed Computing

作者： Yuval Gil Merav Parter Weizmann Institute of Science Rehovot Israel

ISBN: (纸本)9798400718854

We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In this setting, the verifier consists of n nodes connected by a communication graph G. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G satisfies a certain property (e.g., planarity) in a small number of rounds, and with a small communication bound, denoted as the proof *** work by Naor, Parter and Yogev (SODA 2020) presented a DIP for planarity that uses three interaction rounds and a proof size of O (log n). Feuilloley et al. (PODC 2020) showed that the same can be achieved with a single interaction round and without randomization, by providing a proof labeling scheme with a proof size of O (log n). In this work, we design new DIPs that use exponentially shorter proofs compared to the state-of-the-art bounds. Our main results are:• There is a 5-round protocol with O (log log n) proof size for outerplanarity.• There is a 5-round protocol with O (log log n) proof size for verifying embedded planarity and O (log log n + log Δ) proof size for general planar graphs, where Δ is the maximum degree in the graph. In the former setting, it is assumed that an embedding of the graph is given (e.g., each node holds a clockwise orientation of its neighbors) and the goal is to verify that it is a valid planar embedding. The latter result should be compared with the non-interactive setting for which there is lower bound of Ω (log n) bits for graphs with Δ = O(1) by Feuilloley et al. (PODC 2020).• The non-interactive deterministic lower bound of Ω (log n) bits by Feuilloley et al. (PODC 2020) can be extended to hold even if the verifier is randomized. Moreover, the lower bound holds even with the assumption that the verifier's randomness comes in the form of an unbounded random string shared among the nod

关键词： distributed interactive proofs

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：