Shared randomness in locally checkable problems: the role of computational assumptions
From MaRDI portal
Cites work
- Almost global problems in the LOCAL model
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Distributed Computing: A Locality-Sensitive Approach
- Distributed degree splitting, edge coloring, and orientations
- scientific article; zbMATH DE number 1769898 (Why is no real title available?)
- scientific article; zbMATH DE number 5485579 (Why is no real title available?)
- Is it easier to prove theorems that are guaranteed to be true?
- Locality in Distributed Graph Algorithms
- Locally checkable labelings with small messages
- Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols
- Network Decomposition and Distributed Derandomization (Invited Paper)
- On the complexity of the parity argument and other inefficient proofs of existence
- On the Use of Randomness in Local Distributed Graph Algorithms
- On total functions, existence theorems and computational complexity
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Shared randomness helps with local distributed problems
- The distributed complexity of locally checkable labeling problems beyond paths and trees
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- The journey from NP to TFNP hardness
- What Can be Computed Locally?
This page was built for publication: Shared randomness in locally checkable problems: the role of computational assumptions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346881)
