A hierarchy of local decision
DOI10.1016/J.TCS.2020.12.017zbMATH Open1476.68100OpenAlexW2963272893MaRDI QIDQ2219059FDOQ2219059
Authors: Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen 
Publication date: 19 January 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6253/
Recommendations
local modeldistributed decisionlocal certificationproof-labeling schemedistributed hierarchydistributed non-determinism
Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)
Cites Work
- Computational Complexity
- Proof labeling schemes
- Distributed Computing: A Locality-Sensitive Approach
- Distributed verification and hardness of distributed approximation
- Computability in anonymous networks: revocable vs. irrecovable outputs
- The polynomial-time hierarchy
- Locality in Distributed Graph Algorithms
- What cannot be computed locally!
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Leveraging Linial’s Locality Limit
- The local detection paradigm and its applications to self-stabilization
- Distributed verification of minimum spanning trees
- Title not available (Why is that?)
- Survey of local algorithms
- On the Impact of Identifiers on Local Decision
- What Can be Computed Locally?
- Local approximability of max-min and min-max linear programs
- Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
- Towards a complexity theory for local distributed computing
- Survey of distributed decision
- What can be decided locally without identifiers?
- What can be verified locally?
- Distributed graph automata
- Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
- Distributedly testing cycle-freeness
- Transient fault detectors
- Locality and checkability in wait-free computing
- Locally checkable proofs in distributed computing
- Randomized proof-labeling schemes
- Observing self-stabilization
- On distributed Merlin-Arthur decision protocols
- Interactive distributed proofs
- Proof-labeling schemes: broadcast, unicast and in between
- Redundancy in distributed proofs
- The power of distributed verifiers in interactive proofs
- Approximate proof-labeling schemes
- Error-sensitive proof-labeling schemes
- Trade-offs in distributed interactive proofs
- Local verification of global proofs
- Brief announcement: What can be computed without communication?
Cited In (17)
- Deciding and verifying network properties locally with few output bits
- Introduction to local certification
- Local certification of graphs with bounded genus
- Title not available (Why is that?)
- What can be verified locally?
- Minimizing the number of opinions for fault-tolerant distributed decision using well-quasi orderings
- Locally checkable proofs in distributed computing
- Title not available (Why is that?)
- Locally checkable proofs
- What can be verified locally?
- A meta-theorem for distributed certification
- On the Impact of Identifiers on Local Decision
- Hierarchical decision procedure
- What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
- The hardness of local certification of finite-state dynamics
- What can be decided locally without identifiers?
- A meta-theorem for distributed certification
This page was built for publication: A hierarchy of local decision
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2219059)
