4 citations · 7 across the 2 of their papers we have counts for
4 papers
Non-Signaling Proofs with Provers are in PSPACE
Dhiraj Holden, Yael Kalai
Non-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power…
Doubly-Efficient Pseudo-Deterministic Proofs
Michel Goemans, Shafi Goldwasser, Dhiraj Holden
In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time…
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…
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…