Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ERAN GAT :
All reports by Author eran gat :

TR11-136 | 12th October 2011
eran gat , shafi goldwasser

Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications

Revisions: 1

In this paper we introduce a new type of probabilistic search algorithm, which we call the
{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,
and to produce a correct and {\it unique} solution with high probability.
We argue the applicability of such algorithms ... more >>>




ISSN 1433-8092 | Imprint