2 citations · 3 across the 8 of their papers we have counts for
8 papers
Meta-Theorems for Cuttable Distributed Problems
Marthe Bonamy, Avinandan Das, Cyril Gavoille +3
We prove that given any -approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an -round -approximation LOCAL algorithm…
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…
Orientation does not help with 3-coloring a grid in online-LOCAL
Thomas Boudier, Filippo Casagrande, Avinandan Das +4
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know o…
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…
Problems on One Way Road Networks
Jammigumpula Ajaykumar, Avinandan Das, Navaneeta Saikia +1
Let be a One Way Road Network where and are the sets of directed horizontal and vertical roads respectively. can be c…