2 citations · 5 across the 8 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…
cs.DS2024
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…