2 citations · 5 across the 8 of their papers we have counts for
14 papers
The Power of the Score Sequence of a Tournament
Prantar Ghosh, Sahil Kuchlous, Shravan Mehra +1
What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs…
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Sepehr Assadi, Prantar Ghosh, Bruno Loff +2
The following question arises naturally in the study of graph streaming algorithms: "Is there any graph problem which is "not too hard", in that it can be solved efficiently with t…
New Algorithms and Lower Bounds for Streaming Tournaments
Prantar Ghosh, Sahil Kuchlous
We study fundamental directed graph (digraph) problems in the streaming model. An initial investigation by Chakrabarti, Ghosh, McGregor, and Vorotnikova [SODA'20] on streaming digr…
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
Prantar Ghosh, Vihan Shah
We show new lower bounds in the \emph{Merlin-Arthur} (MA) communication model and the related \emph{annotated streaming} or stream verification model. The MA communication model is…
Low-Memory Algorithms for Online and W-Streaming Edge Coloring
Prantar Ghosh, Manuel Stoeckl
For edge coloring, the online and the W-streaming models seem somewhat orthogonal: the former needs edges to be assigned colors immediately after insertion, typically without any s…
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh +1
In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially…
A New Dynamic Algorithm for Densest Subhypergraphs
Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari +1
Computing a dense subgraph is a fundamental problem in graph mining, with a diverse set of applications ranging from electronic commerce to community detection in social networks.…
Adversarially Robust Coloring for Graph Streams
Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may…
Vertex Ordering Problems in Directed Graph Streams
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor +1
We consider directed graph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sort…
New Verification Schemes for Frequency-Based Functions on Data Streams
Prantar Ghosh
We study the general problem of computing frequency-based functions, i.e., the sum of any given function of data stream frequencies. Special cases include fundamental data stream p…
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud…
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models
Suman K. Bera, Amit Chakrabarti, Prantar Ghosh
We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model…
Coloring in Graph Streams
Suman Kalyan Bera, Prantar Ghosh
In this paper, we initiate the study of the vertex coloring problem of a graph in the semi streaming model. In this model, the input graph is defined by a stream of edges, arriving…
Oriented Bipartite Graphs and the Goldbach Graph
Sandip Das, Prantar Ghosh, Shamik Ghosh +1
In this paper, we study oriented bipartite graphs. In particular, we introduce "bitransitive" graphs. Several characterizations of bitransitive bitournaments are obtained. We show…