Copertina

New Hardness Results for the LOCAL Model via a Simple Self-Reduction

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Balliu, Alkida, Casagrande, Filippo, d'Amore, Francesco, Olivetti, Dennis
Natura:	Preprint
Pubblicazione:	2025
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

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

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

Distributed Algorithms for Potential Problems
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)

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

Phase transition of the 3-majority opinion dynamics with noisy interactions
di: d'Amore, Francesco, et al.
Pubblicazione: (2021)

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

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

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

On the Limits of Distributed Quantum Computing
di: d'Amore, Francesco
Pubblicazione: (2025)

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

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

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

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

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

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

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

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

Search via Parallel Lévy Walks on $\mathbb{Z}^2$
di: Clementi, Andrea, et al.
Pubblicazione: (2020)

On the $h$-majority dynamics with many opinions
di: d'Amore, Francesco, et al.
Pubblicazione: (2025)

DejaVu: A Minimalistic Mechanism for Distributed Plurality Consensus
di: d'Amore, Francesco, et al.
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice
di: Cai, Guangya
Pubblicazione: (2025)

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

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)