Pseudodeterministic Constructions in Subexponential Time

by Igor Carboni Oliveira amd Rahul Santhanam

Oded's comments

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.

The original abstract

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.