Local verification of global proofs

DOI10.4230/LIPICS.DISC.2018.25MaRDI QIDQ5090917zbMATH OpenFDO

Authors Laurent Feuilloley, Juho Hirvonen

Publication date 21 July 2022

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

zbMATH Keywords

distributed verificationlocal proofsnon-determinismproof-labeling schemes

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11) Specification and verification (program logics, model checking, etc.) (68Q60) Distributed algorithms (68W15)

Recommendations

• Proof labeling schemes
• Proof labeling schemes
• Locally checkable proofs
• Locally checkable proofs in distributed computing
• Redundancy in distributed proofs

Cites work

• Algorithms, games, and the internet
• Approximate proof-labeling schemes
• Communication Complexity
• Distributed verification of minimum spanning trees
• Error-sensitive proof-labeling schemes
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• scientific article; zbMATH DE number 6820307 (Why is no real title available?)
• Introduction to algorithms.
• Local Distributed Decision
• Locally checkable proofs in distributed computing
• Non-deterministic graph property testing
• Non-interactive proofs of proximity
• Proof labeling schemes
• Proof labeling schemes
• Proof-labeling schemes: broadcast, unicast and in between
• Survey of distributed decision
• The landscape of communication complexity classes
• Towards a complexity theory for local distributed computing
• Worst-case equilibria

Cited in

(11)

• Compact distributed certification of planar graphs
• A hierarchy of local decision
• Locally checkable proofs
• Locally checkable proofs in distributed computing
• Introduction to local certification
• Redundancy in distributed proofs
• Local Proofs for Global Safety Properties
• The hardness of local certification of finite-state dynamics
• Renaming in distributed certification
• Brief announcement: Global certification via perfect hashing
• A LOCAL view of the polynomial hierarchy

This page was built for publication: Local verification of global proofs

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