Proof-labeling schemes: broadcast, unicast and in between

DOI10.1016/j.tcs.2022.05.006OpenAlexW2748863227WikidataQ113863152 ScholiaQ113863152MaRDI QIDQ2672621

Boaz Patt-Shamir, Mor Perry

Publication date: 13 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.06947

zbMATH Keywords

verification complexitycongested cliqueCONGEST modelproof-labeling schemes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast and compact self-stabilizing verification, computation, and fault detection of an MST
• Node labels in local decision
• Space-time tradeoffs for distributed verification
• Distributed verification of minimum spanning trees
• Randomized proof-labeling schemes
• Redundancy in distributed proofs
• Proof labeling schemes
• Locality and checkability in wait-free computing
• The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model
• Locally checkable proofs
• On the power of the congested clique model
• Distributedly Testing Cycle-Freeness
• Edge-Disjoint Spanning Trees of Finite Graphs
• Smallest-last ordering and clustering and graph coloring algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Communication Complexity
• Distributed Verification and Hardness of Distributed Approximation
• The Power of Distributed Verifiers in Interactive Proofs
• What can be decided locally without identifiers?
• Interactive Distributed Proofs
• Towards a complexity theory for local distributed computing
• On the Impact of Identifiers on Local Decision
• Decomposition of Finite Graphs Into Forests

This page was built for publication: Proof-labeling schemes: broadcast, unicast and in between