Proof-labeling schemes: broadcast, unicast and in between

DOI10.1007/978-3-319-69084-1_1MaRDI QIDQ5045429zbMATH OpenOpenAlexFDO

Authors Boaz Patt-Shamir, Mor Perry

Publication date 4 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-69084-1_1

zbMATH Keywords

CONGEST modelcongested cliqueproof-labeling schemesverification complexity

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Proof labeling schemes
• Randomized proof-labeling schemes
• Approximate proof-labeling schemes
• Proof labeling schemes
• Randomized proof-labeling schemes

Cited in

(14)

• Redundancy in distributed proofs
• A hierarchy of local decision
• Proof-labeling schemes: broadcast, unicast and in between
• Introduction to local certification
• Redundancy in distributed proofs
• Local verification of global proofs
• The impact of locality in the broadcast congested clique model
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Invited Paper: Reactive PLS for Distributed Decision
• Communication efficient self-stabilizing leader election
• Twenty-two new approximate proof labeling schemes
• Locally verifiable distributed SNARGs
• Connectivity lower bounds in broadcast congested clique
• The message complexity of distributed graph optimization

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5045429)