4 citations · 11 across the 8 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.CC2019★ 2 cited
Pseudo-deterministic Streaming
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty +1
A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Clas…
cs.DS2019
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…
cs.DC2019
Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators
Lijie Chen, Ofer Grossman
We develop techniques to prove lower bounds for the BCAST(log n) Broadcast Congested Clique model (a distributed message passing model where in each round, each processor can broad…