Pseudodeterministic Constructions in Subexponential Time

Igor C. Oliveira, Rahul Santhanam

We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infi…