4 citations · 10 across the 4 of their papers we have counts for
4 papers · 1 filter
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
Ofer Grossman, Meghal Gupta, Mark Sellke
We investigate one of the most basic problems in streaming algorithms: approximating the number of elements in the stream. In 1978, Morris famously gave a randomized algorithm achi…
Strategy-Stealing is Non-Constructive
Greg Bodwin, Ofer Grossman
In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing. This work is about the…
Algorithms for Noisy Broadcast under Erasures
Ofer Grossman, Bernhard Haeupler, Sidhanth Mohanty
The noisy broadcast model was first studied in [Gallager, TranInf'88] where an -character input is distributed among processors, so that each processor receives one input bi…
Improved Deterministic Distributed Construction of Spanners
Ofer Grossman, Merav Parter
Graph spanners are fundamental graph structures with a wide range of applications in distributed networks. We consider a standard synchronous message passing model where in each ro…