Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with unique solution:
TR12-101 | 10th August 2012
Oded Goldreich, Shafi Goldwasser, Dana Ron

On the possibilities and limitations of pseudodeterministic algorithms

We study the possibilities and limitations
of pseudodeterministic algorithms,
a notion put forward by Gat and Goldwasser (2011).
These are probabilistic algorithms that solve search problems
such that on each input, with high probability, they output
the same solution, which may be thought of as a canonical solution.
We consider ... more >>>

TR17-140 | 11th September 2017
Tong Qin, Osamu Watanabe

An improvement of the algorithm of Hertli for the unique 3SAT problem

We propose a simple idea for improving the randomized algorithm of Hertli for the Unique 3SAT problem.

more >>>

TR18-022 | 1st February 2018
Omer Reingold, Guy Rothblum, Ron Rothblum

Efficient Batch Verification for UP

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... more >>>

ISSN 1433-8092 | Imprint