Proof-labeling schemes: broadcast, unicast and in between

DOI10.1007/978-3-319-69084-1_1zbMATH Open1498.68023OpenAlexW2963368942MaRDI QIDQ5045429FDOQ5045429

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

Recommendations

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

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)

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)