5 papers
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…
One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
Avinandan Das
This paper investigates the semi-streaming complexity of \textit{-partial coloring}, a generalization of proper graph coloring. For , a -partial coloring requires t…
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…
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…
Semi-Streaming Algorithms for Graph Property Certification
Avinandan Das, Pierre Fraigniaud, Ami Paz +1
We introduce the {\em certification} of solutions to graph problems when access to the input is restricted. This topic has received a lot of attention in the distributed computing…