2 citations · 2 across the 4 of their papers we have counts for
12 papers · 1 filter
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…
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.…