Copertina

Is a LOCAL algorithm computable?

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Cruciani, Antonio, Das, Avinandan, Equi, Massimo, Lievonen, Henrik, Luong-Le, Diep, Modanese, Augusto, Suomela, Jukka
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Distributed, Parallel, and Cluster Computing Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Orientation does not help with 3-coloring a grid in online-LOCAL
di: Boudier, Thomas, et al.
Pubblicazione: (2025)

It does not matter how you define locally checkable labelings
di: Cruciani, Antonio, et al.
Pubblicazione: (2026)

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

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

Local problems in trees across a wide range of distributed models
di: Dhar, Anubhav, et al.
Pubblicazione: (2024)

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

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

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

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

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

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

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

Maintaining a Bounded Degree Expander in Dynamic Peer-to-Peer Networks
di: Cruciani, Antonio
Pubblicazione: (2025)

Analog computation with transcriptional networks
di: Doty, David, et al.
Pubblicazione: (2025)

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

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
di: Balliu, Alkida, et al.
Pubblicazione: (2026)

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

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

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

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

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

Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
di: Bok, Jan, et al.
Pubblicazione: (2025)

Strong and Hiding Distributed Certification of Bipartiteness
di: Jauregui, Benjamin, et al.
Pubblicazione: (2025)

Distributed Computation with Local Advice
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

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

Distributed Algorithms for Potential Problems
di: Balliu, Alkida, et al.
Pubblicazione: (2025)

Highly Dynamic and Fully Distributed Data Structures
di: Augustine, John, et al.
Pubblicazione: (2024)

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

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

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

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

It's Hard to HAC with Average Linkage!
di: Bateni, MohammadHossein, et al.
Pubblicazione: (2024)

Segmented Operations using Matrix Multiplications
di: Sobczyk, Aleksandros, et al.
Pubblicazione: (2025)

Parallel Hierarchical Agglomerative Clustering in Low Dimensions
di: Bateni, MohammadHossein, et al.
Pubblicazione: (2025)

Work-Efficient Parallel Counting via Sampling
di: Liu, Hongyang, et al.
Pubblicazione: (2024)

2-Coloring Cycles in One Round
di: Flin, Maxime, et al.
Pubblicazione: (2026)

To Store or Not to Store: a graph theoretical approach for Dataset Versioning
di: Guo, Anxin, et al.
Pubblicazione: (2024)

Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions
di: d'Amore, Francesco, et al.
Pubblicazione: (2020)

The Singular Optimality of Distributed Computation in LOCAL
di: Dufoulon, Fabien, et al.
Pubblicazione: (2024)