论文标题
本地限制的证明标签方案（完整版）
Locally Restricted Proof Labeling Schemes (Full Version)
论文作者
论文摘要
由Korman，Kutten和Peleg引入（PODC 2005），证明标签方案（PLS）是一个分布式验证系统，用于评估给定的配置图是否满足某个属性。它涉及一个集中式的摊子，其作用是提供证据表明，给定的配置图是通过将标签分配给节点的是是的，而分布式验证者则是通过对分配标签的本地访问来验证给定证明的有效性的作用。在本文中，我们介绍了局部限制的PL的概念，其中供供众的功率仅限于具有多个回合数量的局部算法的概念。为了规避本地限制设置中PLS的固有可能性，我们转向模型，通过允许验证者接受一些不存在的模型，只要它们与满足所讨论的属性不太“太远”。为此，我们根据近似证明标记方案（APLS）的概念评估（1）分布式图优化问题（OPTDGPS）（类似于顺序近似算法中使用的弛豫类型）； （2）基于发现的证明标签方案（TPLS）的概念（类似于属性测试算法中使用的弛豫类型），配置了图族（CGFS）。
Introduced by Korman, Kutten, and Peleg (PODC 2005), a proof labeling scheme (PLS) is a distributed verification system dedicated to evaluating if a given configured graph satisfies a certain property. It involves a centralized prover, whose role is to provide proof that a given configured graph is a yes-instance by means of assigning labels to the nodes, and a distributed verifier, whose role is to verify the validity of the given proof via local access to the assigned labels. In this paper, we introduce the notion of a locally restricted PLS in which the prover's power is restricted to that of a LOCAL algorithm with a polylogarithmic number of rounds. To circumvent inherent impossibilities of PLSs in the locally restricted setting, we turn to models that relax the correctness requirements by allowing the verifier to accept some no-instances as long as they are not "too far" from satisfying the property in question. To this end, we evaluate (1) distributed graph optimization problems (OptDGPs) based on the notion of an approximate proof labeling scheme (APLS) (analogous to the type of relaxation used in sequential approximation algorithms); and (2) configured graph families (CGFs) based on the notion of atesting proof labeling schemes (TPLS) (analogous to the type of relaxation used in property testing algorithms).
