All reports by Author Dhiraj Holden:

__
TR19-135
| 2nd October 2019
__

Michel Goemans, Shafi Goldwasser, Dhiraj Holden#### Doubly-Efficient Pseudo-Deterministic Proofs

__
TR17-105
| 14th June 2017
__

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden#### Pseudo-Deterministic Proofs

__
TR16-140
| 9th September 2016
__

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan#### On SZK and PP

Revisions: 3

__
TR16-056
| 8th April 2016
__

Shafi Goldwasser, Dhiraj Holden#### On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances

__
TR14-176
| 16th December 2014
__

Eric Allender, Dhiraj Holden, Valentine Kabanets#### The Minimum Oracle Circuit Size Problem

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 verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions ... more >>>

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 same output on different executions.

As in the case with classical interactive proofs,

the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

Shafi Goldwasser, Dhiraj Holden

We set out to study the impact of having access to correlated instances on the fine grained complexity of polynomial time problems, which have notoriously resisted improvement.

In particular, we show how to use a logarithmic number of auxiliary correlated instances to obtain $o(n^2)$ time algorithms for the longest common ...
more >>>

Eric Allender, Dhiraj Holden, Valentine Kabanets

We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP$^{QBF}$ is known to be complete for PSPACE under ZPP reductions. We show that it is not ... more >>>