1 citations · 1 across the 9 of their papers we have counts for
4 papers · 1 filter
Simulating Random Walks in Random Streams
John Kallaugher, Michael Kapralov, Eric Price
The random order graph streaming model has received significant attention recently, with problems such as matching size estimation, component counting, and the evaluation of bounde…
Factorial Lower Bounds for (Almost) Random Order Streams
Ashish Chiplunkar, John Kallaugher, Michael Kapralov +1
In this paper we introduce and study the \textsc{StreamingCycles} problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental i…
A Quantum Advantage for a Natural Streaming Problem
John Kallaugher
Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [S…
An Optimal Algorithm for Triangle Counting in the Stream
Rajesh Jayaram, John Kallaugher
We present a new algorithm for approximating the number of triangles in a graph whose edges arrive as an arbitrary order stream. If is the number of edges in , the n…