1 citations · 3 across the 5 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
cs.DS2024
Space Complexity of Minimum Cut Problems in Single-Pass Streams
Matthew Ding, Alexandro Garces, Jason Li +4
We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the spec…
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…