Gillat Kol

activity

20192022

collaborators

5 papers

cs.DS2022

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 $n$ players corresponding…

cs.LG2021

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 $Q = {q_{1}, \dots, q_{n}}$ of distributions, and a sampling access to an unknown tar…

cs.DS2021

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs

Lijie Chen, Gillat Kol, Dmitry Paramonov +3

For a directed graph $G$ with $n$ vertices and a start vertex $u_{start}$ , we wish to (approximately) sample an $L$ -step random walk over $G$ starting from $u_{start}$ with…

cs.DS2020

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 $2$ -regular $n$ -vertex graph $G$ are arriving one-by-one in a stream and we are promised th…

cs.DS2019

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~ $U \subseteq R^{d}$ of size $∣ U ∣ = n$ . T…