Locally checkable proofs

DOI10.1145/1993806.1993829MaRDI QIDQ2943393zbMATH OpenOpenAlexFDO

Authors Mika Göös, Jukka Suomela

Publication date 11 September 2015

Published in Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10138/28213

zbMATH Keywords

proof complexitydecision problemslocal algorithmsgraph propertiesnondeterministic algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Recommendations

• Locally checkable proofs in distributed computing
• Local verification of global proofs
• A hierarchy of local decision
• scientific article; zbMATH DE number 6820307
• What Can be Computed Locally?

Cites work

• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• Almost-Everywhere Secure Computation
• Broadcasting in dynamic radio networks
• Consensus algorithms with one-bit messages
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Fault Tolerance in Networks of Bounded Degree
• Flooding time in edge-Markovian dynamic graphs
• Gradient clock synchronization in dynamic networks
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Knowledge and common knowledge in a distributed environment
• Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
• Optimal gradient clock synchronization in dynamic networks
• Parsimonious flooding in dynamic graphs
• Perfectly secure message transmission
• Programming simultaneous actions using common knowledge
• Reaching Agreement in the Presence of Faults

Cited in

(14)

• How proofs are prepared at Camelot (extended abstract)
• Deciding and verifying network properties locally with few output bits
• A hierarchy of local decision
• A new approach on locally checkable problems
• Locally checkable proofs in distributed computing
• Local verification of global proofs
• Local soundness for QBF calculi
• Locality and checkability in wait-free computing
• Locality and checkability in wait-free computing
• What can be verified locally?
• Proof-labeling schemes: broadcast, unicast and in between
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Local mending

This page was built for publication: Locally checkable proofs

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