2017/07/18 by Holden, Dhiraj
#68Q15 #Computational Complexity (cs.CC) #F.1.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1707.05808
We show the first unconditional pseudo-determinism result for all of search-BPP. Specifically, we show that every BPP search problem can be computed pseudo-deterministically on average for infinitely many input lengths. In other words, for infinitely many input lengths and for any polynomial-time samplable distribution our algorithm succeeds in producing a unique answer (if one exists) with high probability over the distribution and the coins tossed.