Imagen de Portada

Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bok, Jan, Das, Avinandan, Gujgiczer, Anna, Jedličková, Nikola
Formato:	Preprint
Publicado:	2025
Materias:	Distributed, Parallel, and Cluster Computing Computational Complexity Discrete Mathematics F.2.2; G.2.2
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
por: Lingas, Andrzej
Publicado: (2026)

A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs
por: Cook, Linda, et al.
Publicado: (2025)

A Note on Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds of the Congested Clique
por: Lingas, Andrzej
Publicado: (2024)

GenTT: Generate Vectorized Codes for General Tensor Permutation
por: Chen, Yaojian, et al.
Publicado: (2025)

Clock Synchronization Is Almost Impossible with Bounded Memory
por: Charron-Bost, Bernadette, et al.
Publicado: (2024)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
por: Bartlett, Celina Janet
Publicado: (2025)

On Minimum Maximal Distance-k Matchings
por: Kartynnik, Yury, et al.
Publicado: (2016)

Sublinear-Time Sampling of Spanning Trees in the Congested Clique
por: Pemmaraju, Sriram V., et al.
Publicado: (2024)

Obfuscated Consensus
por: Aspnes, James, et al.
Publicado: (2025)

Why Canonical Rounds Fail for Optimal Byzantine Resilience
por: Attiya, Hagit, et al.
Publicado: (2025)

Improving Efficiency in Near-State and State-Optimal Self-Stabilising Leader Election Population Protocols
por: Gąsieniec, Leszek, et al.
Publicado: (2025)

Anonymous Self-Stabilising Localisation via Spatial Population Protocols
por: Gąsieniec, Leszek, et al.
Publicado: (2024)

An Analysis of Avalanche Consensus
por: Amores-Sesar, Ignacio, et al.
Publicado: (2024)

The consensus number of a shift register equals its width
por: Aspnes, James
Publicado: (2025)

Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed Systems
por: Galeana, Hugo Rincon, et al.
Publicado: (2023)

Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity
por: Gupta, Chetan, et al.
Publicado: (2024)

Complexity of Firefighting on Graphs
por: Althoetmar, Julius, et al.
Publicado: (2025)

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

Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique
por: Lingas, Andrzej
Publicado: (2024)

Near-Optimal Wafer-Scale Reduce
por: Luczynski, Piotr, et al.
Publicado: (2024)

Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
por: Kowalski, Dariusz R., et al.
Publicado: (2025)

Distributed Rhombus Formation of Sliding Squares
por: Kostitsyna, Irina, et al.
Publicado: (2025)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
por: Fairbairn, David L., et al.
Publicado: (2024)

In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs
por: Casteigts, Arnaud, et al.
Publicado: (2023)

Decentralized Distributed Graph Coloring: Cluster Graphs
por: Flin, Maxime, et al.
Publicado: (2024)

The Complexity of Blocking All Solutions
por: Grüne, Christoph, et al.
Publicado: (2025)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
por: Grüne, Christoph, et al.
Publicado: (2023)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
por: Istrate, Gabriel
Publicado: (2024)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
por: Grüne, Christoph, et al.
Publicado: (2024)

FedMon: Federated eBPF Monitoring for Distributed Anomaly Detection in Multi-Cluster Cloud Environments
por: Zehra, Sehar, et al.
Publicado: (2025)

Coloring Hardness on Low Twin-Width Graphs
por: Bonnet, Édouard
Publicado: (2025)

On Finding Randomly Planted Cliques in Arbitrary Graphs
por: Agrimonti, Francesco, et al.
Publicado: (2025)

A Decomposition Approach to the Weighted $k$-server Problem
por: Ayyadevara, Nikhil, et al.
Publicado: (2024)

Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs
por: Faour, Salwa, et al.
Publicado: (2025)

High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing
por: Maas, Nikolai
Publicado: (2026)

Gathering Semi-Synchronously Scheduled Two-State Robots
por: Otaka, Kohei, et al.
Publicado: (2024)

Low-Depth Spatial Tree Algorithms
por: Baumann, Yves, et al.
Publicado: (2024)

Data Scheduling Algorithm for Scalable and Efficient IoT Sensing in Cloud Computing
por: Mohammad, Noor Islam S.
Publicado: (2025)

RadiK: Scalable and Optimized GPU-Parallel Radix Top-K Selection
por: Li, Yifei, et al.
Publicado: (2025)

Simple, strict, proper, happy: A study of reachability in temporal graphs
por: Casteigts, Arnaud, et al.
Publicado: (2022)