4 citations · 11 across the 8 of their papers we have counts for
10 papers
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…
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…
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…
Pseudo-deterministic Proofs
Shafi Goldwasser, Ofer Grossman, Dhiraj Holden
We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the sam…
Amplification and Derandomization Without Slowdown
Ofer Grossman, Dana Moshkovitz
We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most…