论文标题
具有有限属的图表的本地认证
Local Certification of Graphs with Bounded Genus
论文作者
论文摘要
NAOR，PARTER和YOGEV [SODA 2020]最近设计了一种编译器，用于自动将标准的集中交互式协议转换为分布式交互式协议，如KOL，OSHMAN和SAXENA [PODC 2018]。 In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a $\mathsf{dMAM}(O(\log n))$ protocol for this class, that is, a distributed interactive protocol with $O(\log n)$-bit proof size in $n$-node graphs, and three interactions between the (centralizer) computationally-unbounded but不可信的称者Merlin和（分散的）随机计算验证者Arthur。作为推论，有一个$ \ mathsf {dmam}（o（\ log n））$协议，用于平面图类别，以及带有有限属的图形类别。 我们证明，存在一个分布式的交互式协议，用于与界面的构造属类别的分布式交互协议，仅执行一个相互作用，从供供者到验证者，但保留了$ o（\ log n）$ bits的证明大小。该结果也适用于具有有界demi-genus的图形类别，即可以嵌入在有界属的不可方向表面上的图。本文描述的交互式协议实际上是证明标记的方案，即交互式协议的子类，以前是Korman，Kutten和Peleg [PODC 2005]。特别是，这些方案不需要从验证者那里进行任何随机化，并且通常以低成本的节点本身将证据计算为先验。因此，我们的结果扩大了Feuilloley等人的最新平面图证明标记方案。 [PODC 2020]，到有界属的图和界面的象征。
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a $\mathsf{dMAM}(O(\log n))$ protocol for this class, that is, a distributed interactive protocol with $O(\log n)$-bit proof size in $n$-node graphs, and three interactions between the (centralizer) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a $\mathsf{dMAM}(O(\log n))$ protocol for the class of planar graphs, as well as for the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of $O(\log n)$ bits. This result also holds for the class of graphs with bounded demi-genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded demigenus.
