A hierarchy of local decision
From MaRDI portal
Publication:2219059
Recommendations
Cites work
- scientific article; zbMATH DE number 1375591 (Why is no real title available?)
- Approximate proof-labeling schemes
- Brief announcement: What can be computed without communication?
- Computability in anonymous networks: revocable vs. irrecovable outputs
- Computational Complexity
- Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Distributed graph automata
- Distributed verification and hardness of distributed approximation
- Distributed verification of minimum spanning trees
- Distributedly testing cycle-freeness
- Error-sensitive proof-labeling schemes
- Interactive distributed proofs
- Leveraging Linial’s Locality Limit
- Local approximability of max-min and min-max linear programs
- Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
- Local verification of global proofs
- Locality and checkability in wait-free computing
- Locality in Distributed Graph Algorithms
- Locally checkable proofs in distributed computing
- Observing self-stabilization
- On distributed Merlin-Arthur decision protocols
- On the Impact of Identifiers on Local Decision
- Proof labeling schemes
- Proof-labeling schemes: broadcast, unicast and in between
- Randomized proof-labeling schemes
- Redundancy in distributed proofs
- Survey of distributed decision
- Survey of local algorithms
- The local detection paradigm and its applications to self-stabilization
- The polynomial-time hierarchy
- The power of distributed verifiers in interactive proofs
- Towards a complexity theory for local distributed computing
- Trade-offs in distributed interactive proofs
- Transient fault detectors
- What Can be Computed Locally?
- What can be decided locally without identifiers?
- What can be verified locally?
- What cannot be computed locally!
Cited in
(17)- Deciding and verifying network properties locally with few output bits
- Introduction to local certification
- Local certification of graphs with bounded genus
- scientific article; zbMATH DE number 7075933 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 6820307 (Why is no real title available?)
- 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
- A meta-theorem for distributed certification
- The hardness of local certification of finite-state dynamics
- What can be decided locally without identifiers?
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)
