Approximate Proof-Labeling Schemes
| Autor: | Ami Paz, Mor Perry, Keren Censor-Hillel |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
010201 computation theory & mathematics Computer science 0202 electrical engineering electronic engineering information engineering Approximation algorithm 020206 networking & telecommunications Maximum size 0102 computer and information sciences 02 engineering and technology Network configuration Topology 01 natural sciences Predicate (grammar) |
| Zdroj: | Structural Information and Communication Complexity ISBN: 9783319720494 SIROCCO |
| DOI: | 10.1007/978-3-319-72050-0_5 |
| Popis: | We study a new model of verification of boolean predicates over distributed networks. Given a network configuration, the proof-labeling scheme (PLS) model defines a distributed proof in the form of a label that is given to each node, and all nodes locally verify that the network configuration satisfies the desired boolean predicate by exchanging labels with their neighbors. The proof size of the scheme is defined to be the maximum size of a label. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|