论文标题
22个新的近似证明标签方案（完整版）
Twenty-Two New Approximate Proof Labeling Schemes (Full Version)
论文作者
论文摘要
由Korman，Kutten和Peleg引入（分布式计算2005），A \ Emph {证明标记方案（PLS）}是一个专门用于验证给定配置图是否满足某个属性的系统。 它由集中式\ emph {prover}组成，其作用是以将标签分配给节点的形式和分布式\ emph {verifier}生成是证明，其作用是通过局部手段来验证证明的有效性，并仅在属性满足属性时就可以验证证明的有效性。 为了克服某些图形属性的PLS标签大小的下限，审查员，PAZ和Perry（Sirocco 2017）介绍了\ emph {近似证明标签方案（APLS）}的概念，该概念允许验证者同样接受某些不可能的事物，只要他们不满足“不满意”。
Introduced by Korman, Kutten, and Peleg (Distributed Computing 2005), a \emph{proof labeling scheme (PLS)} is a system dedicated to verifying that a given configuration graph satisfies a certain property. It is composed of a centralized \emph{prover}, whose role is to generate a proof for yes-instances in the form of an assignment of labels to the nodes, and a distributed \emph{verifier}, whose role is to verify the validity of the proof by local means and accept it if and only if the property is satisfied. To overcome lower bounds on the label size of PLSs for certain graph properties, Censor-Hillel, Paz, and Perry (SIROCCO 2017) introduced the notion of an \emph{approximate proof labeling scheme (APLS)} that allows the verifier to accept also some no-instances as long as they are not "too far" from satisfying the property.
