Source author record

Dhiraj Holden

Dhiraj Holden appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Computational Geometry Data Structures and Algorithms quant-ph

Catalog footprint

What is connected

3works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Doubly-Efficient Pseudo-Deterministic Proofs

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 are possible. They showed that whereas there exists a constant round pseudo deterministic proof for graph isomorphism where the canonical solution is the lexicographically smallest isomorphism, the existence of pseudo-deterministic interactive proofs for NP-hard problems would imply the collapse of the polynomial time hierarchy. In this paper, we turn our attention to studying doubly-efficient pseudo-deterministic proofs for polynomial time search problems: pseudo-deterministic proofs with the extra requirement that the prover runtime is polynomial and the verifier runtime to verify that a solution is canonical is significantly lower than the complexity of finding any solution, canonical or otherwise. Naturally this question is particularly interesting for search problems for which a lower bound on its worst case complexity is known or has been widely conjectured. We show doubly-efficient pseudo-deterministic algorithms for a host of natural problems whose complexity has long been conjectured. In particular, we show a doubly efficient pseudo-deterministic NP proof for linear programming, 3-SUM and problems reducible to 3-SUM, the hitting set problem, and the Zero Weight Triangle problem and show a doubly-efficient pseudo-deterministic MA proof for the Orthogonal Vectors problem and the $k$-Clique problem.

preprint2020arXiv

Non-Signaling Proofs with $O(\sqrt{\log n})$ Provers are in PSPACE

Non-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power of no-signaling proofs. It is known that 2-prover no-signaling proofs are characterized by PSPACE, and that no-signaling proofs with $poly(n)$-provers are characterized by EXP. However, the power of $k$-prover no-signaling proofs, for $2<k<poly(n)$ remained an open problem. We show that $k$-prover no-signaling proofs (with negligible soundness) for $k=O(\sqrt{\log n})$ are contained in PSPACE. We prove this via two different routes that are of independent interest. In both routes we consider a relaxation of no-signaling called sub-no-signaling. Our main technical contribution (which is used in both our proofs) is a reduction showing how to convert any sub-no-signaling strategy with value at least $1-2^{-Ω(k^2)}$ into a no-signaling one with value at least $2^{-O(k^2)}$. In the first route, we show that the classical prover reduction method for converting $k$-prover games into $2$-prover games carries over to the no-signaling setting with the following loss in soundness: if a $k$-player game has value less than $2^{-ck^2}$ (for some constant~$c>0$), then the corresponding 2-prover game has value at most $1 - 2^{dk^2}$ (for some constant~$d>0$). In the second route we show that the value of a sub-no-signaling game can be approximated in space that is polynomial in the communication complexity and exponential in the number of provers.

preprint2014arXiv

Fast algorithmic self-assembly of simple shapes using random agitation

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 with rigid-body movement rules (push/pull, deterministically and programmatically applied to specific monomers) and random agitations (nondeterministically applied to every monomer and direction with equal probability all of the time). Previous work on the nubot model showed how to build simple shapes such as lines and squares quickly---in expected time that is merely logarithmic of their size. These results crucially make use of the programmable rigid-body movement rule: the ability for a single monomer to control the movement of a large objects quickly, and only at a time and place of the programmers' choosing. However, in engineered molecular systems, molecular motion is largely uncontrolled and fundamentally random. This raises the question of whether similar results can be achieved in a more restrictive, and perhaps easier to justify, model where uncontrolled random movements, or agitations, are happening throughout the self-assembly process and are the only form of rigid-body movement. We show that this is indeed the case: we give a polylogarithmic expected time construction for squares using agitation, and a sublinear expected time construction to build a line. Such results are impossible in an agitation-free (and movement-free) setting and thus show the benefits of exploiting uncontrolled random movement.