GMGopinath Mishra

Gopinath Mishra

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Gopinath Mishra has a total of 36 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Optimal (degree+1)-Coloring in Congested Clique

    by Sam Coy, Artur Czumaj, Peter Davies, Gopinath Mishra

    We consider the distributed complexity of the ( degree + 1 )-list coloring problem, in which each node [Formula: see text] of degree [Formula: see text] is assigned a palette of [Formula: see text] colors, and the goal is to find a proper coloring using these color palettes. The ( degree + 1 )-list coloring problem is a natural generalization of the classical [Formula: see text]-coloring and [Formula: see text]-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing. In this paper, we settle the complexity of the ( degree + 1 )-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.

  • Open Access

    On Parallel k -Center Clustering

    by Sam Coy, Artur Czumaj, Gopinath Mishra

    We consider the classic \( k \) -center problem in the constant dimensional Euclidean space under a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model, with local space per machine of \(\mathcal{O}(n^{\delta})\) , where \(\delta\in(0,1)\) is an arbitrary constant. As a central clustering problem, the \( k \) -center problem has been studied extensively. Still, until very recently, all parallel MPC algorithms have been requiring \(\Omega(k)\) or even \(\Omega(kn^{\delta})\) local space per machine. While this setting covers the case of small values of \( k \) , for a large number of clusters these algorithms require large local memory, making them poorly scalable. The case of large \( k \) , \(k\geq\Omega(n^{\delta})\) , has been considered recently for the low-local-space MPC model by Bateni et al. [2021], who gave an \(\mathcal{O}(\log\log n)\) -round MPC algorithm that produces \(k(1+o(1))\) centers whose cost has multiplicative approximation of \(\mathcal{O}(\log\log\log n)\) . In this article, we extend the algorithm of Bateni et al. and design a low-local-space MPC algorithm that in \(\mathcal{O}(\log\log n)\) rounds returns a clustering with \(k(1+o(1))\) clusters that is an \(\mathcal{O}(\log^{*}n)\) -approximation for \( k \) -center.

  • Open Access

    Parallel derandomization for coloring

    by Sam Coy, Artur Czumaj, Peter Davies-Peck, Gopinath Mishra


  • Open Access

    Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

    by Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen

  • Open Access

    Round and Communication Efficient Graph Coloring

    by Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, Farrel D Salim


  • Open Access

    Brief Announcement: The Complexity Landscape of Dynamic Distributed Subgraph Finding

    by Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, Mingyang Yang

  • Open Access

    Optimal Distributed Replacement Paths

    by Yi-Jun Chang, Yanyu Chen, Dipan Dey, Gopinath Mishra, Hung Thuan Nguyen, Bryce Sanchez

  • Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing

    by Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

    The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently drawn samples from an oracle. The testing task is to distinguish a distribution that satisfies some property from a distribution that is far in some distance measure from satisfying it. The task of tolerant testing imposes a further restriction, that distributions close to satisfying the property are also accepted. This work focuses on the connection between the sample complexities of non-tolerant testing of distributions and their tolerant testing counterparts. When limiting our scope to label-invariant (symmetric) properties of distributions, we prove that the gap is at most quadratic, ignoring poly-logarithmic factors. Conversely, the property of being the uniform distribution is indeed known to have an almost-quadratic gap. When moving to general, not necessarily label-invariant properties, the situation is more complicated, and we show some partial results. We show that if a property requires the distributions to be non-concentrated, that is, the probability mass of the distribution is sufficiently spread out, then it cannot be non-tolerantly tested with $o(\sqrt {n})$ many samples, where n denotes the universe size. Clearly, this implies at most a quadratic gap, because a distribution can be learned (and hence tolerantly tested against any property) using $\mathcal {O}(n)$ many samples. Being non-concentrated is a strong requirement on properties, as we also prove a close to linear lower bound against their tolerant tests. Apart from the case where the distribution is non-concentrated, we also show if an input distribution is very concentrated, in the sense that it is mostly supported on a subset of size s of the universe, then it can be learned using only $\mathcal {O}(s)$ many samples. The learning procedure adapts to the input, and works without knowing s in advance.


  • Open Access

    Parallel Derandomization for Coloring (Abstract) | Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing

    by Sam Coy, Artur Czumaj, Peter Davies-Peck, Gopinath Mishra

    Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designing efficient deterministic algorithms for these problems has been found particularly challenging. In this work we consider this challenge, and design a novel framework for derandomizing algorithms for coloring-type problems in the Massively Parallel Computation (MPC) model with sublinear space. We give an application of this framework by showing that a recent (degree+1)-list coloring algorithm by Halldorsson et al. (STOC'22) in the LOCAL model of distributed computation can be translated to the MPC model and efficiently derandomized. Our algorithm runs in O(łog łog łog n) rounds, which matches the complexity of the state of the art algorithm for the (Δ + 1)-coloring problem.

  • Open Access

    A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model

    by Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, Mingyang Yang, Yu-Cheng Yeh

    Recently, Akbari et al. (ICALP 2023) studied the locality of graph problems in distributed, sequential, dynamic, and online settings from a unified point of view. They designed a novel O(log n)-locality deterministic algorithm for proper 3-coloring bipartite graphs in the Online-LOCAL model. In this work, we establish the optimality of the algorithm by showing a tight deterministic Ω (log n) locality lower bound, which holds even on grids. To complement this result, we have the following additional results: (1) We show a higher and tight [EQUATION] lower bound for 3-coloring toroidal and cylindrical grids. (2) Considering the generalization of 3-coloring bipartite graphs to (k+1)-coloring k-partite graphs, we show that the problem also has O(log n) locality when the input is a k-partite graph that admits a locally inferable unique coloring. This special class of k-partite graphs covers several fundamental graph classes such as k-trees and triangular grids. Moreover, for this special class of graphs, we show a tight Ω(log n) locality lower bound. (3) For general k-partite graphs with k ≥ 3, we prove that the problem of (2k − 2)-coloring k-partite graphs exhibits a locality of Ω(n) in the Online-LOCAL model, matching the round complexity of the same problem in the LOCAL model recently shown by Coiteux-Roy et al. (STOC 2024). Consequently, the problem of (k + 1)-coloring k-partite graphs admits a locality lower bound of Ω(n) when k ≥ 3, contrasting sharply with the Θ(log n) locality for the case of k = 2.