Randomized proof-labeling schemes

DOI10.1145/2767386.2767421MaRDI QIDQ2796267zbMATH OpenOpenAlexFDO

Authors Mor Baruch, Pierre Fraigniaud, Boaz Patt-Shamir

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

communication complexitydistributed verification

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(20)

• Approximate proof-labeling schemes
• Fooling views: a new lower bound technique for distributed computations under congestion
• Error-sensitive proof-labeling schemes
• Approximate proof-labeling schemes
• Redundancy in distributed proofs
• Shared versus private randomness in distributed interactive proofs
• Proof-carrying data from arithmetized random oracles
• Compact distributed certification of planar graphs
• A Randomized Algorithm for BBCSPs in the Prover-Verifier Model
• Connectivity lower bounds in broadcast congested clique
• Proof-labeling schemes: broadcast, unicast and in between
• Proof labeling schemes
• Proof labeling schemes
• Proof-labeling schemes: broadcast, unicast and in between
• Invited Paper: Reactive PLS for Distributed Decision
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Randomized proof-labeling schemes
• Twenty-two new approximate proof labeling schemes
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• Randomized proofs in arithmetic

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

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