Randomized proof-labeling schemes
type: Item
instance of: scholarly article
title: Randomized proof-labeling schemes
zbMATH Open document ID: 1452.68024
author: Pierre Fraigniaud
author: Boaz Patt-Shamir
author: Mor Perry
published in: Distributed Computing
publication date: 2019-07-11T00:00:00Z
full work available at URL: podc9.pdf
Mathematics Subject Classification ID: 68M14
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 7079200
zbMATH Keywords: distributed verification
zbMATH Keywords: communication complexity
zbMATH Keywords: proof-labeling schemes
zbMATH Keywords: non-determinism
zbMATH Keywords: randomized algorithms
MaRDI profile type: Publication
OpenAlex ID: W2889545431
cites work: The local detection paradigm and its applications to self-stabilization
cites work: Labeling Schemes for Small Distances in Trees
cites work: Nearest common ancestors: a survey and a new algorithm for a distributed environment
cites work: Distributedly Testing Cycle-Freeness
cites work: Reachability and Distance Queries via 2-Hop Labels
cites work: Q4598260
cites work: Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
cites work: Q4535803
cites work: Q4736828
cites work: Randomized distributed decision
cites work: What can be decided locally without identifiers?
cites work: On the Impact of Identifiers on Local Decision
cites work: Node labels in local decision
cites work: Towards a complexity theory for local distributed computing
cites work: Locality and checkability in wait-free computing
cites work: A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring
cites work: Q4796196
cites work: Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
cites work: Distance labeling in graphs
cites work: Q3179347
cites work: Implicat Representation of Graphs
cites work: Q4778559
cites work: Labeling Schemes for Flow and Connectivity
cites work: Distance labeling schemes for well-separated graph classes
cites work: Labeling Schemes for Vertex Connectivity
cites work: Distributed verification of minimum spanning trees
cites work: Fast and compact self-stabilizing verification, computation, and fault detection of an MST
cites work: Proof labeling schemes
cites work: Constructing labeling schemes through universal matrices
cites work: Communication Complexity
cites work: Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
cites work: Space-time tradeoffs for distributed verification
cites work: Q4944965
cites work: Informative labeling schemes for graphs
cites work: Distributed Verification and Hardness of Distributed Approximation
cites work: Depth-First Search and Linear Graph Algorithms
Wikidata QID: Q129321306
DOI: 10.1007/S00446-018-0340-8
description: scientific article; zbMATH DE number 7079200