Zobrazeno 1 - 10
of 26
pro vyhledávání: '"Holden, Dhiraj"'
Autor:
Holden, Dhiraj
In this thesis, we study several extensions of the concept of interactive proofs. First, we consider non-signaling multi-prover interactive proofs. Interacting with multiple non-interacting provers increases the ability of the verifier to check the s
Externí odkaz:
https://hdl.handle.net/1721.1/143142
Autor:
Holden, Dhiraj, Kalai, Yael
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
Externí odkaz:
http://arxiv.org/abs/1910.02590
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 studie
Externí odkaz:
http://arxiv.org/abs/1910.00994
Autor:
Holden, Dhiraj
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.
Cataloged from PDF version of thesis.
Includes bibliographical references (page 39).
Instances of computational probl
Cataloged from PDF version of thesis.
Includes bibliographical references (page 39).
Instances of computational probl
Externí odkaz:
http://hdl.handle.net/1721.1/111915
Autor:
Holden, Dhiraj
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 average for infinitely many input lengths. In other words, for infinitely
Externí odkaz:
http://arxiv.org/abs/1707.05808
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 intera
Externí odkaz:
http://arxiv.org/abs/1706.04641
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 SZK contains hard problems, by exhibiting an oracle relative to which SZ
Externí odkaz:
http://arxiv.org/abs/1609.02888
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 progra
Externí odkaz:
http://arxiv.org/abs/1409.4828
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We introduce pseudo-deterministic interactive proofs (psdIP): 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 intera
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fd77dc5b0c693415c32d5621b3654912