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

non-determinismdistributed verificationlocal proofsproof-labeling schemes

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• scientific article; zbMATH DE number 6820307 (Why is no real title available?)
• Algorithms, games, and the internet
• Approximate proof-labeling schemes
• Communication Complexity
• Distributed verification of minimum spanning trees
• Error-sensitive proof-labeling schemes
• 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

(8)

• Introduction to local certification
• A hierarchy of local decision
• Locally checkable proofs in distributed computing
• Locally checkable proofs
• Redundancy in distributed proofs
• Compact distributed certification of planar graphs
• Local Proofs for Global Safety Properties
• The hardness of local certification of finite-state dynamics

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)