3 papers
cs.DS2026
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…
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…