Cover Image

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Balliu, Alkida, Brandt, Sebastian, Kuhn, Fabian, Olivetti, Dennis, Picavet, Timothé, Schmid, Gustav
Format:	Preprint
Published:	2026
Subjects:	Distributed, Parallel, and Cluster Computing Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Completing the Node-Averaged Complexity Landscape of LCLs on Trees
by: Balliu, Alkida, et al.
Published: (2024)

Towards Fully Automatic Distributed Lower Bounds
by: Balliu, Alkida, et al.
Published: (2024)

New Hardness Results for the LOCAL Model via a Simple Self-Reduction
by: Balliu, Alkida, et al.
Published: (2025)

On the Node-Averaged Complexity of Locally Checkable Problems on Trees
by: Balliu, Alkida, et al.
Published: (2023)

Distributed Quantum Advantage in Locally Checkable Labeling Problems
by: Balliu, Alkida, et al.
Published: (2025)

Distributed Algorithms for Potential Problems
by: Balliu, Alkida, et al.
Published: (2025)

Tight Lower Bounds in the Supported LOCAL Model
by: Balliu, Alkida, et al.
Published: (2024)

Distributed Computation with Local Advice
by: Balliu, Alkida, et al.
Published: (2024)

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
by: Balliu, Alkida, et al.
Published: (2025)

On the Universality of Round Elimination Fixed Points
by: Balliu, Alkida, et al.
Published: (2025)

Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
by: Balliu, Alkida, et al.
Published: (2024)

Distributed Quantum Advantage for Local Problems
by: Balliu, Alkida, et al.
Published: (2024)

Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs
by: Balliu, Alkida, et al.
Published: (2024)

Shared Randomness Helps with Local Distributed Problems
by: Balliu, Alkida, et al.
Published: (2024)

Distributed $(Δ+1)$-Coloring in Graphs of Bounded Neighborhood Independence
by: Fuchs, Marc, et al.
Published: (2025)

A Review on Message Complexity of the Algorithms for Clock Synchronization in Distributed Systems
by: Dissanayake, Chandeepa, et al.
Published: (2024)

Tightening I/O Lower Bounds through the Hourglass Dependency Pattern
by: Eyraud-Dubois, Lionel, et al.
Published: (2024)

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

LCLs Beyond Bounded Degrees
by: Schmid, Gustav
Published: (2026)

Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
by: Bonamy, Marthe, et al.
Published: (2025)

Is a LOCAL algorithm computable?
by: Cruciani, Antonio, et al.
Published: (2026)

Matrix Multiplication in the MPC Model
by: Joshi, Lakshya, et al.
Published: (2025)

Meta-Theorems for Cuttable Distributed Problems
by: Bonamy, Marthe, et al.
Published: (2026)

The Adaptive Complexity of Finding a Stationary Point
by: Zhou, Huanjian, et al.
Published: (2025)

Algorithmics and Complexity of Cost-Driven Task Offloading with Submodular Optimization in Edge-Cloud Environments
by: Guo, Longkun, et al.
Published: (2024)

No distributed quantum advantage for approximate graph coloring
by: Coiteux-Roy, Xavier, et al.
Published: (2023)

Classification of Local Optimization Problems in Directed Cycles
by: Boudier, Thomas, et al.
Published: (2026)

Multiparty equality in the local broadcast model
by: Esperet, Louis, et al.
Published: (2025)

A Post-Quantum Lower Bound for the Distributed Lovász Local Lemma
by: Brandt, Sebastian, et al.
Published: (2025)

Distributed Triangle Detection is Hard in Few Rounds
by: Assadi, Sepehr, et al.
Published: (2025)

Online Locality Meets Distributed Quantum Computing
by: Akbari, Amirreza, et al.
Published: (2024)

On the Decidability of Distributed Tasks with Output Sets under Asynchrony and Any Number of Crashes
by: Albouy, Timothé, et al.
Published: (2026)

Testing Spreading Behavior in Networks with Arbitrary Topologies
by: Modanese, Augusto, et al.
Published: (2023)

Robust predicate and function computation in continuous chemical reaction networks
by: Calabrese, Kim, et al.
Published: (2025)

Is stochastic thermodynamics the key to understanding the energy costs of computation?
by: Wolpert, David, et al.
Published: (2023)

Analog computation with transcriptional networks
by: Doty, David, et al.
Published: (2025)

Towards Optimal Deterministic LOCAL Algorithms on Trees
by: Brandt, Sebastian, et al.
Published: (2025)

Exploring the Landscape of Distributed Graph Sketching
by: Tench, David, et al.
Published: (2024)

A Modular Approach to Construct Signature-Free BRB Algorithms under a Message Adversary
by: Albouy, Timothé, et al.
Published: (2022)

Topological Characterization of Consensus in Distributed Systems
by: Nowak, Thomas, et al.
Published: (2019)