The general problem considered here is obtaining pseudodeterministic (or better deterministic) algorithms for finding elements in a dense set that is in P (e.g., the set of prime numbers). The point is that repeated sampling can be used to find such elements, but it may not yield the same output in all successful runs (or even in most of them). The current work provides an algorithm that outputs a canonical element in sub-exponential time on infinitely many input lengths.

Actually, the result is stronger: Two hitting set generators are provided, and it is shown that at least one of them works. The first one is a polynomial-time pseudodeterministic algorithm and the second is a deterministic subexponential time algorithm. It is shown that it is either the case that the first algorithm works (for each dense set in P) on almost all input lengths or the second algorithm works (for each dense set in P) on infinitely many input length.

This undetermined either-or result arises from a use of a win-win technique. Specifically, failure of the first algorithm can be translated into a hardness result (regarding BPE), and this hardness result can be used towards getting a pseudodeterministic algorithm (rather than a deterministic algorithm).

Other variants on the basic technique yield related results that bound the gaps between the input lengths in the i.o.-side at the cost of increasing a negligible error probability.

**Digest (based on discussion with Roei Tell, 21/12/16):**
(The following description is a simplified version that is only
implicit in the text and yields a weaker (in some sense) result.)
The deterministic subexponentail-time algorithm
is based on a pseudorandom generator that relies on
the assumption that PSPACE contains a set not in BPP
(this uses [Trevisan and Vadhan 2007],
which in turn builds on [Impagliazzo, Wigderson 2001]).
The pseudodeterministic polynomial-time algorithm is based
on a second pseudorandom generator, which in turn is based
on the observation that a PSPACE algorithm can find the
truth-table of the lexicographcaly-first function, defined
on logarithmicly long strings, that is hard for circuits
of polynomial-size (where the polynomial bounding the size
is smaller than the one bounding the spacde complexity).
Now, if (contrary to common beliefs...) the assumption
underlying the [TV07/IW01] pseudorandom generator does not hold
(i.e., if PSPACE is contained in BPP),
then this truthtable can be constructed by a PPT algorithm
(i.e., this search problem can be solved by a pseudodeterministic
polynomial-time algorithm by reduction to finding its bits in BPP).
Plugged into the IW97/NW construction,
this yields the other pseudorandom generator.
The pseudodeterministic algorithm for the search problem
first finds this function, then invopkes the corresponding
pseudorandom generator on all seeds, and finally outputs
the lexicographically-first solution it obtains.
Note that in this description the said function is found
with very high probability (i.e., error occurs with negligible
probability, but not with probability zero).

**An afterthought (22/12/16):**
Actually, there is no need to go through NW/IW97:
Just consider the task of constructing a polynomial-size sample space
that fools all polynomial-size circuits (again a smaller poly);
indeed, this yields a non-uniform pseudorandom generator
(just as the one we used via NW/IW).
This task can be solved a PSPACE,
hence by pseudodeterministic poly-time algorithm
(via PSPACE in BPP and error reduction as before...).
But actually (and more radically), we don't need to pass
via pseudorandom generators at all (in the case PSPACE is BPP).
Fixing any search-BPP problem
(as defined in HERE),
consider the task of finding the lex-first solution to a given input.
This task (or rather finding the bits of this solution) is in PSPACE,
and so in BPP, and so has it a pseudodeterministic poly-time algorithm....

**Comment from the authors (22/12/16):**
We actually use the idea of the radical afterthought
(in the case PSPACE=BPP) in the proof of the result
where we bound the gaps between the input lengths in the i-o side.

We study *pseudodeterministic constructions*, i.e., randomized
algorithms which output the *same solution* on most computation paths.
We establish unconditionally that there is an infinite sequence $\{p_n\}_{n
\in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$
running in expected sub-exponential time such that for each $n$, on input
$1^{|p_n|}$, $A$ outputs $p_n$ with probability $1$. In other words, our
result provides a pseudodeterministic construction of primes in
sub-exponential time which works infinitely often.

This result follows from a much more general theorem about pseudodeterministic constructions. A property $Q \subseteq \{0,1\}^{*}$ is $\gamma$-dense if for large enough $n$, $|Q \cap \{0,1\}^n| \geq \gamma 2^n$. We show that for each $c > 0$ at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family $\{H_n\}$ of sets, $H_n \subseteq \{0,1\}^n$, such that for each $(1/n^c)$-dense property $Q \in DTIME(n^c)$ and every large enough $n$, $H_n \cap Q \neq \emptyset$; or (2) There is a deterministic sub-exponential time construction of a family $\{H'_n\}$ of sets, $H'_n \subseteq \{0,1\}^n$, such that for each $(1/n^c)$-dense property $Q \in DTIME(n^c)$ and for infinitely many values of $n$, $H'_n \cap Q \neq \emptyset$.

We provide further algorithmic applications that might be of independent interest. Perhaps intriguingly, while our main results are unconditional, they have a non-constructive element, arising from a sequence of applications of the hardness versus randomness paradigm.

See ECCC TR16-196.

Back to list of Oded's choices.