Copertina

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

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bok, Jan, Das, Avinandan, Gujgiczer, Anna, Jedličková, Nikola
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Distributed, Parallel, and Cluster Computing Computational Complexity Discrete Mathematics F.2.2; G.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

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

Obfuscated Consensus
di: Aspnes, James, et al.
Pubblicazione: (2025)

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

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

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

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

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

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

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

Complexity of Firefighting on Graphs
di: Althoetmar, Julius, et al.
Pubblicazione: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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