4 citations · 10 across the 4 of their papers we have counts for
8 papers
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
Yuval Efron, Ofer Grossman, Seri Khoury
By far the most fruitful technique for showing lower bounds for the CONGEST model is reductions to two-party communication complexity. This technique has yielded nearly tight resul…
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…
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…
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…
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…
Reproducibility and Pseudo-Determinism in Log-Space
Ofer Grossman, Yang P. Liu
A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the resul…