4 citations · 7 across the 4 of their papers we have counts for
6 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…
On the Power of Statistical Zero Knowledge
Adam Bouland, Lijie Chen, Dhiraj Holden +2
We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZ…
Fast algorithmic self-assembly of simple shapes using random agitation
Ho-Lin Chen, David Doty, Dhiraj Holden +3
We study the power of uncontrolled random molecular movement in the nubot model of self-assembly. The nubot model is an asynchronous nondeterministic cellular automaton augmented w…