The hardness of local certification of finite-state dynamics
From MaRDI portal
Publication:6547916
DOI10.1007/978-3-031-55598-5_4MaRDI QIDQ6547916
Pedro Montealegre, Martín Ríos-Wilson, Diego Maldonado
Publication date: 31 May 2024
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Simple dynamics on graphs
- Computational complexity of threshold automata networks under different updating schemes
- Complexity of reachability problems for finite discrete dynamical systems
- What can be verified locally?
- Randomized proof-labeling schemes
- Redundancy in distributed proofs
- Local certification of graphs on surfaces
- A meta-theorem for distributed certification
- A hierarchy of local decision
- On the stability and instability of finite dynamical systems with prescribed interaction graphs
- Proof labeling schemes
- Beeping a maximal independent set
- Convergence in (Social) Influence Networks
- A Biological Solution to a Fundamental Distributed Computing Problem
- Deploying Wireless Networks with Beeps
- Communication Complexity
- The Power of Distributed Verifiers in Interactive Proofs
- Stone age distributed computing
- Interactive Distributed Proofs
- What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
- Local Certification of Graph Decompositions and Applications to Minor-Free Classes
- On the influence of the interaction graph on a finite dynamical system
- Trade-offs in distributed interactive proofs
- Distributed zero-knowledge proofs over networks
This page was built for publication: The hardness of local certification of finite-state dynamics
