Randomized proof-labeling schemes

DOI10.1007/s00446-018-0340-8zbMath1452.68024OpenAlexW2889545431WikidataQ129321306 ScholiaQ129321306MaRDI QIDQ2002054

Mor Perry, Boaz Patt-Shamir, Pierre Fraigniaud

Publication date: 11 July 2019

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01247352/file/podc9.pdf

zbMATH Keywords

randomized algorithmscommunication complexitynon-determinismdistributed verificationproof-labeling schemes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (11)

Proof-labeling schemes: broadcast, unicast and in between ⋮ Distributed Testing of Distance-k Colorings ⋮ Unnamed Item ⋮ A hierarchy of local decision ⋮ A meta-theorem for distributed certification ⋮ Redundancy in distributed proofs ⋮ Compact distributed certification of planar graphs ⋮ A meta-theorem for distributed certification ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Local certification of graphs with bounded genus ⋮ Introduction to local certification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast and compact self-stabilizing verification, computation, and fault detection of an MST
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• Constructing labeling schemes through universal matrices
• The local detection paradigm and its applications to self-stabilization
• Node labels in local decision
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Space-time tradeoffs for distributed verification
• Distance labeling schemes for well-separated graph classes
• Distributed verification of minimum spanning trees
• Randomized distributed decision
• A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring
• Proof labeling schemes
• Locality and checkability in wait-free computing
• Informative labeling schemes for graphs
• Distributedly Testing Cycle-Freeness
• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• Implicat Representation of Graphs
• Reachability and Distance Queries via 2-Hop Labels
• Labeling Schemes for Flow and Connectivity
• Distance labeling in graphs
• Communication Complexity
• Distributed Verification and Hardness of Distributed Approximation
• What can be decided locally without identifiers?
• Towards a complexity theory for local distributed computing
• Labeling Schemes for Vertex Connectivity
• Labeling Schemes for Small Distances in Trees
• On the Impact of Identifiers on Local Decision
• Depth-First Search and Linear Graph Algorithms
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds

This page was built for publication: Randomized proof-labeling schemes