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

verification complexitycongested cliqueCONGEST modelproof-labeling schemes

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(12)

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

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)