Buchumschlag

Shared Randomness Helps with Local Distributed Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian, Modanese, Augusto, Olivetti, Dennis, Rabie, Mikaël, Suomela, Jukka, Uitto, Jara
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Distributed, Parallel, and Cluster Computing
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
von: Balliu, Alkida, et al.
Veröffentlicht: (2024)

Distributed Computation with Local Advice
von: Balliu, Alkida, et al.
Veröffentlicht: (2024)

Distributed Algorithms for Potential Problems
von: Balliu, Alkida, et al.
Veröffentlicht: (2025)

On the Universality of Round Elimination Fixed Points
von: Balliu, Alkida, et al.
Veröffentlicht: (2025)

Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs
von: Balliu, Alkida, et al.
Veröffentlicht: (2024)

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
von: Balliu, Alkida, et al.
Veröffentlicht: (2025)

Towards Fully Automatic Distributed Lower Bounds
von: Balliu, Alkida, et al.
Veröffentlicht: (2024)

Completing the Node-Averaged Complexity Landscape of LCLs on Trees
von: Balliu, Alkida, et al.
Veröffentlicht: (2024)

Distributed Quantum Advantage in Locally Checkable Labeling Problems
von: Balliu, Alkida, et al.
Veröffentlicht: (2025)

Distributed Quantum Advantage for Local Problems
von: Balliu, Alkida, et al.
Veröffentlicht: (2024)

Tight Lower Bounds in the Supported LOCAL Model
von: Balliu, Alkida, et al.
Veröffentlicht: (2024)

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
von: Balliu, Alkida, et al.
Veröffentlicht: (2026)

Classification of Local Optimization Problems in Directed Cycles
von: Boudier, Thomas, et al.
Veröffentlicht: (2026)

On the Node-Averaged Complexity of Locally Checkable Problems on Trees
von: Balliu, Alkida, et al.
Veröffentlicht: (2023)

New Hardness Results for the LOCAL Model via a Simple Self-Reduction
von: Balliu, Alkida, et al.
Veröffentlicht: (2025)

Local problems in trees across a wide range of distributed models
von: Dhar, Anubhav, et al.
Veröffentlicht: (2024)

Is a LOCAL algorithm computable?
von: Cruciani, Antonio, et al.
Veröffentlicht: (2026)

Distributed Coloring in the SLEEPING Model
von: Dufoulon, Fabien, et al.
Veröffentlicht: (2024)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
von: Baumecker, Malte, et al.
Veröffentlicht: (2025)

A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
von: Cambus, Mélanie, et al.
Veröffentlicht: (2022)

It does not matter how you define locally checkable labelings
von: Cruciani, Antonio, et al.
Veröffentlicht: (2026)

Meta-Theorems for Cuttable Distributed Problems
von: Bonamy, Marthe, et al.
Veröffentlicht: (2026)

Strong and Hiding Distributed Certification of Bipartiteness
von: Jauregui, Benjamin, et al.
Veröffentlicht: (2025)

Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions
von: Hadad, Adar, et al.
Veröffentlicht: (2025)

On the Locality of Hall's Theorem
von: Brandt, Sebastian, et al.
Veröffentlicht: (2025)

Online Locality Meets Distributed Quantum Computing
von: Akbari, Amirreza, et al.
Veröffentlicht: (2024)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2024)

Adaptive Massively Parallel Coloring in Sparse Graphs
von: Latypov, Rustam, et al.
Veröffentlicht: (2024)

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2024)

Parallel Dynamic Maximal Matching
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2024)

Testing Spreading Behavior in Networks with Arbitrary Topologies
von: Modanese, Augusto, et al.
Veröffentlicht: (2023)

On Optimizing Resource Utilization in Distributed Connected Components
von: Esfahani, Mohsen Koohi
Veröffentlicht: (2025)

Biased Compression in Gradient Coding for Distributed Learning
von: Li, Chengxi, et al.
Veröffentlicht: (2026)

2-Coloring Cycles in One Round
von: Flin, Maxime, et al.
Veröffentlicht: (2026)

No distributed quantum advantage for approximate graph coloring
von: Coiteux-Roy, Xavier, et al.
Veröffentlicht: (2023)

Do MPI Derived Datatypes Actually Help? A Single-Node Cross-Implementation Study on Shared-Memory Communication
von: Adefemi, Temitayo
Veröffentlicht: (2025)

Leveraging Structural Knowledge for Solving Election in Anonymous Networks with Shared Randomness
von: Chalopin, Jérémie, et al.
Veröffentlicht: (2026)

CXL Shared Memory Programming: Barely Distributed and Almost Persistent
von: Xu, Yi, et al.
Veröffentlicht: (2024)

A Cut-Matching Game for Constant-Hop Expanders
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2022)