Showing cs.DCShow all
3 papers · 1 filter
cs.DC2026
Is a LOCAL algorithm computable?
Antonio Cruciani, Avinandan Das, Massimo Equi +4
Common definitions of the "standard" LOCAL model tend to be sloppy and even self-contradictory on one point: do the nodes update their state using an arbitrary function or a comput…
cs.DC2026
It does not matter how you define locally checkable labelings
Antonio Cruciani, Avinandan Das, Alesya Raevskaya +1
Locally checkable labeling problems (LCLs) form the foundation of the modern theory of distributed graph algorithms. First introduced in the seminal paper by Naor and Stockmeyer [S…
cs.DC2025
Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
Jan Bok, Avinandan Das, Anna Gujgiczer +1
We investigate the classical and distributed complexity of \emph{-partial -coloring} where , a natural generalization of Brooks' theorem where each vertex should be colo…