4 citations · 10 across the 4 of their papers we have counts for
3 papers · 1 filter
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…
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…
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…