Locally checkable proofs

DOI10.1145/1993806.1993829zbMath1321.68465OpenAlexW2065963401MaRDI QIDQ2943393

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

decision problemsgraph propertiesproof complexitylocal algorithmsnondeterministic 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)

Related Items (10)

What can be verified locally? ⋮ Proof-labeling schemes: broadcast, unicast and in between ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ Locality and checkability in wait-free computing ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Deciding and verifying network properties locally with few output bits ⋮ Randomized distributed decision ⋮ Locality and Checkability in Wait-Free Computing ⋮ Local mending ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

Cites Work

• Unnamed Item
• Gradient clock synchronization in dynamic networks
• Consensus algorithms with one-bit messages
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Broadcasting in dynamic radio networks
• Programming simultaneous actions using common knowledge
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Flooding time in edge-Markovian dynamic graphs
• Knowledge and common knowledge in a distributed environment
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony
• Fault Tolerance in Networks of Bounded Degree
• Reaching Agreement in the Presence of Faults
• Perfectly secure message transmission
• Parsimonious flooding in dynamic graphs
• Optimal gradient clock synchronization in dynamic networks
• Almost-Everywhere Secure Computation

This page was built for publication: Locally checkable proofs