3 citations · 6 across the 4 of their papers we have counts for
6 papers
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…
Statistically Near-Optimal Hypothesis Selection
Olivier Bousquet, Mark Braverman, Klim Efremenko +2
Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class of distributions, and a sampling access to an unknown tar…
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…