3 citations · 6 across the 4 of their papers we have counts for
5 papers · 1 filter
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams
Sepehr Assadi, Gillat Kol, Zhijun Zhang
The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over d…
Rounds vs Communication Tradeoffs for Maximal Independent Sets
Sepehr Assadi, Gillat Kol, Zhijun Zhang
We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are players corresponding…
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
Lijie Chen, Gillat Kol, Dmitry Paramonov +3
For a directed graph with vertices and a start vertex , we wish to (approximately) sample an -step random walk over starting from with…
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena +1
Consider the following gap cycle counting problem in the streaming model: The edges of a -regular -vertex graph are arriving one-by-one in a stream and we are promised th…
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
Mark Braverman, Gillat Kol, Shay Moran +1
We study the Convex Set Disjointness (CSD) problem, where two players have input sets taken from an arbitrary fixed domain~ of size . T…