<p>The <a href="https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm" rel="noreferrer">Tonelli–Shanks algorithm</a> for computing square roots modulo primes.</p>
<p>More generally, <a href="https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields" rel="noreferrer">factorization of polynomials over finite fields</a> using the Cantor–Zassenhaus algorithm.</p>
<p>Both can be made pseudodeterministic by canonizing the result in a suitable way (e.g., for square roots, output the unique square root in <span class="math-container">$\{0,\dots,(p-1)/2\}$</span>; for factorization, require the factors to be monic, and output them in some sort of lexicographic order).</p>

CC BY-SA 4.0
2023-07-19T09:34:50.583Z
Though your answer is *technically* correct, I think these are not convincing examples for pseudo-deterministic algorithms, since in both cases, the algorithm is actually computing the only solution to the problem. (For square roots over $ℤ/pℤ$, once you have one, you get the other one; and unique factorization of polynomials over finite fields is, morally, unique.) This is very different from the recent pseudo-deterministic algorithm to compute an $n$-bit prime number.
Bruno
CC BY-SA 4.0
2023-07-19T09:46:48.410Z
So what? Why should a good example be similar to some particular recent algorithm? This reasoning does not make sense to me. These are standard algorithms that are reasonably simple, solve natural problems with practical applications, and they are pesudodeterministic, while no deterministic algorithms are known.
Emil Jeřábek
CC BY-SA 4.0
2023-07-19T12:04:50.417Z
I think that the notion of pseudo-deterministic algorithm really makes sense only for multi-valued function, otherwise it matches the notion of (standard) randomized algorithm. I took the recent algorithm as an example where the notion fully makes sense in my opinion.
Bruno
CC BY-SA 4.0
2023-07-19T12:31:39.447Z
Well, usually different runs of a randomized algorithm compute different outputs. Surprisingly, randomization may sometimes help even with computing things that do not depend on the random bits, and this is what a pseudodeterministic algorithm means. This is equally nontrivial when the search problem formally has other solutions, or when it does not.
Emil Jeřábek
CC BY-SA 4.0
2023-07-19T12:41:07.070Z
Though I admit that all randomized *decision* algorithms are pseudodeterministic in this way, and these are indeed not good examples.
Emil Jeřábek
CC BY-SA 4.0
2023-07-19T12:47:35.940Z
The notion of pseudo-deterministic algorithms (or *Bellagio* algorithms in the original paper) was explicitly defined for search problems. And in the (quickly skimmed) literature, authors refer to pseudo-determinism only for search problem with several solutions. I do not read the term about polynomial factorization for instance.
Bruno
CC BY-SA 4.0
2023-07-19T09:18:13.727Z
2023-07-19T09:18:13.727Z
Emil Jeřábek
<p>Here is a bit artificial example, not sure whether you'll like it:<br />
Given <span class="math-container">$m=pq$</span>, where <span class="math-container">$p$</span> and <span class="math-container">$q$</span> are large primes, and a primitive root <span class="math-container">$g$</span> of <span class="math-container">$\mathbb Z_m^*$</span>, compute <span class="math-container">$1/g$</span> or factorize <span class="math-container">$m$</span>.<br />
Pseudodeterministic algorithm for the problem:<br />
Pick a random <span class="math-container">$x\in \mathbb Z_m$</span>.<br />
Test whether <span class="math-container">$x$</span> and <span class="math-container">$m$</span> are relative primes.<br />
If yes, compute <span class="math-container">$xg, xg^2,\dots$</span> until we get <span class="math-container">$1$</span>.<br />
Unless we stumble upon an <span class="math-container">$x$</span> that is not relative prime to <span class="math-container">$m$</span>, this gives the canonical solution <span class="math-container">$1/g$</span>.<br />
Note that picking a random <span class="math-container">$x$</span>, instead of starting from <span class="math-container">$g$</span>, improves the expected running time of the algorithm by a factor of two.</p>

CC BY-SA 4.0
2023-07-19T09:51:07.193Z
What do you mean by a “primitive root of $\mathbb Z_m^*$”? Under the stated assumptions, $\mathbb Z_m^*$ is not cyclic (unless $p=q$). Anyway, $1/g$ modulo $m$ is easy to compute deterministically.
Emil Jeřábek
CC BY-SA 4.0
2023-07-19T12:10:39.453Z
I know that $1/g$ is easy to compute, but I don't think this should be an issue for a toy example. Not being cyclic is a bigger problem...
domotorp
CC BY-SA 4.0
2023-07-19T07:50:40.200Z
2023-07-19T07:50:40.200Z
domotorp
<p><strong>Definition</strong>. A randomized algorithm for a search problem is <em>pseudodeterministic</em> if it produces a fixed canonical solution to the search problem with high probability.</p>
<p><strong>Question</strong>.  The notion of a pseudodeterministic algorithm is simple enough, but I cannot think of a simple one.  A search on the web only reveals theoretical papers that don't seem to straightforwardly show one.  Can you show me a simple one so that I can see that it is possible (to exist)?</p>

CC BY-SA 4.0
2023-07-20T02:15:27.310Z
In theory, I can't distinguish pseudodeterministic algorithms from [Las Vegas algorithms](https://en.wikipedia.org/wiki/Las_Vegas_algorithm). Noting that [Las Vegas algorithms are the function class version of ZPP](https://cstheory.stackexchange.com/questions/5258/the-multifunction-version-of-zpp), and one [definition of ZPP](https://en.wikipedia.org/wiki/ZPP_(complexity)) is a decision version of your definition. So, is there a difference in theory from Las Vegas algorithms, or only in practice (i.e. one definition emphasizes randomized runtime, the other randomized correctness).
usul
CC BY-SA 4.0
2023-07-20T02:27:08.197Z
Maybe I should explain more directly: if we have a Las Vegas algorithm (randomized runtime, always correct), we can turn it into an algorithm that is correct with high probability and has a deterministic runtime by truncating the computation after a fixed multiple of the expected runtime. If we have a pseudodeterministic algorithm, and we can check correctness of solutions efficiently, then we can turn it into a Las Vegas algorithm by switching to exhaustive search whenever it's incorrect.
usul
CC BY-SA 4.0
2023-07-23T01:49:43.460Z
Good question. Your notice of Las Vegas algorithms makes me think of randomized Quicksort as a pseudodeterministic algorithm because randomized Quicksort makes use of random bits, always produces a fixed sorted list as output with (very) high probability.  I also say that sorting is a search problem in which the universe of search is every permutation of the list of elements to be sorted.  In other words, I'm also unable to distinguish pseudodeterministic from Las Vegas methods.
user69687
CC BY-SA 4.0
2023-07-23T02:01:07.587Z
One thought that comes to mind is that randomized Quicksort is both a pseudodeterministic algorithm and a Las Vegas algorithm.  In other words, Las Vegas is a larger set that contains pseudodeterministic algorithms.  Although randomized Quicksort always produces a fixed sorted list as output, this is not required by the definition of a Las Vegas algorithm.
user69687
CC BY-SA 4.0
2023-07-25T00:43:35.677Z
maybe problems that are not in NP $\inf$ coNP so they are not easy to turn into smallest answer versions (which have unique answers).
Kaveh
<randomized-algorithms>
What is a very simple pseudodeterministic algorithm (for educational purposes)?
user69687
# What is a very simple pseudodeterministic algorithm (for educational purposes)?

(Asked by: username_0 on 2023-07-18)

**Definition**. A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability.

**Question**. The notion of a pseudodeterministic algorithm is simple enough, but I cannot think of a simple one. A search on the web only reveals theoretical papers that don't seem to straightforwardly show one. Can you show me a simple one so that I can see that it is possible (to exist)?

**Tags:** randomized-algorithms
> **Comments:**
> **username_1**: In theory, I can't distinguish pseudodeterministic algorithms from [Las Vegas algorithms](https://en.wikipedia.org/wiki/Las_Vegas_algorithm). Noting that [Las Vegas algorithms are the function class version of ZPP](https://cstheory.stackexchange.com/questions/5258/the-multifunction-version-of-zpp), and one [definition of ZPP](https://en.wikipedia.org/wiki/ZPP_(complexity)) is a decision version of your definition. So, is there a difference in theory from Las Vegas algorithms, or only in practice (i.e. one definition emphasizes randomized runtime, the other randomized correctness).  
> **username_1**: Maybe I should explain more directly: if we have a Las Vegas algorithm (randomized runtime, always correct), we can turn it into an algorithm that is correct with high probability and has a deterministic runtime by truncating the computation after a fixed multiple of the expected runtime. If we have a pseudodeterministic algorithm, and we can check correctness of solutions efficiently, then we can turn it into a Las Vegas algorithm by switching to exhaustive search whenever it's incorrect.  
> **username_0**: Good question. Your notice of Las Vegas algorithms makes me think of randomized Quicksort as a pseudodeterministic algorithm because randomized Quicksort makes use of random bits, always produces a fixed sorted list as output with (very) high probability.  I also say that sorting is a search problem in which the universe of search is every permutation of the list of elements to be sorted.  In other words, I'm also unable to distinguish pseudodeterministic from Las Vegas methods.  
> **username_0**: One thought that comes to mind is that randomized Quicksort is both a pseudodeterministic algorithm and a Las Vegas algorithm.  In other words, Las Vegas is a larger set that contains pseudodeterministic algorithms.  Although randomized Quicksort always produces a fixed sorted list as output, this is not required by the definition of a Las Vegas algorithm.  
> **username_2**: maybe problems that are not in NP $\inf$ coNP so they are not easy to turn into smallest answer versions (which have unique answers).  

---

## 2 answers

### Answer by username_3 on 2023-07-19. Score: 5 | Accepted answer

The [Tonelli–Shanks algorithm](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) for computing square roots modulo primes.

More generally, [factorization of polynomials over finite fields](https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields) using the Cantor–Zassenhaus algorithm.

Both can be made pseudodeterministic by canonizing the result in a suitable way (e.g., for square roots, output the unique square root in $\{0,\dots,(p-1)/2\}$; for factorization, require the factors to be monic, and output them in some sort of lexicographic order).

> **Comments:**
> **username_4**: Though your answer is *technically* correct, I think these are not convincing examples for pseudo-deterministic algorithms, since in both cases, the algorithm is actually computing the only solution to the problem. (For square roots over $ℤ/pℤ$, once you have one, you get the other one; and unique factorization of polynomials over finite fields is, morally, unique.) This is very different from the recent pseudo-deterministic algorithm to compute an $n$-bit prime number.  
> **username_3**: So what? Why should a good example be similar to some particular recent algorithm? This reasoning does not make sense to me. These are standard algorithms that are reasonably simple, solve natural problems with practical applications, and they are pesudodeterministic, while no deterministic algorithms are known.  
> **username_4**: I think that the notion of pseudo-deterministic algorithm really makes sense only for multi-valued function, otherwise it matches the notion of (standard) randomized algorithm. I took the recent algorithm as an example where the notion fully makes sense in my opinion.  
> **username_3**: Well, usually different runs of a randomized algorithm compute different outputs. Surprisingly, randomization may sometimes help even with computing things that do not depend on the random bits, and this is what a pseudodeterministic algorithm means. This is equally nontrivial when the search problem formally has other solutions, or when it does not.  
> **username_3**: Though I admit that all randomized *decision* algorithms are pseudodeterministic in this way, and these are indeed not good examples.  
> **username_4**: The notion of pseudo-deterministic algorithms (or *Bellagio* algorithms in the original paper) was explicitly defined for search problems. And in the (quickly skimmed) literature, authors refer to pseudo-determinism only for search problem with several solutions. I do not read the term about polynomial factorization for instance.  

---

### Answer by username_5 on 2023-07-19. Score: 1

Here is a bit artificial example, not sure whether you'll like it:  
Given $m=pq$, where $p$ and $q$ are large primes, and a primitive root $g$ of $\mathbb Z\_m^\*$, compute $1/g$ or factorize $m$.  
Pseudodeterministic algorithm for the problem:  
Pick a random $x\in \mathbb Z\_m$.  
Test whether $x$ and $m$ are relative primes.  
If yes, compute $xg, xg^2,\dots$ until we get $1$.  
Unless we stumble upon an $x$ that is not relative prime to $m$, this gives the canonical solution $1/g$.  
Note that picking a random $x$, instead of starting from $g$, improves the expected running time of the algorithm by a factor of two.

> **Comments:**
> **username_3**: What do you mean by a “primitive root of $\mathbb Z_m^*$”? Under the stated assumptions, $\mathbb Z_m^*$ is not cyclic (unless $p=q$). Anyway, $1/g$ modulo $m$ is easy to compute deterministically.  
> **username_5**: I know that $1/g$ is easy to compute, but I don't think this should be an issue for a toy example. Not being cyclic is a bigger problem...  

---

