Gillat Kol

activity

20192023

most citedMulti-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

3 citations · 6 across the 4 of their papers we have counts for

collaborators

Showing 2021Show all

2 papers · 1 filter

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…