4 citations · 7 across the 4 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017★ 3 cited
A Note on Unconditional Subexponential-time Pseudo-deterministic Algorithms for BPP Search Problems
Dhiraj Holden
We show the first unconditional pseudo-determinism result for all of search-BPP. Specifically, we show that every BPP search problem can be computed pseudo-deterministically on ave…
cs.CC2017★ 4 cited
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…