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 >>>

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

more >>>

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 >>>