On Pseudodeterministic Approximation Algorithms

We investigate the notion of pseudodeterminstic approximation algorithms. A randomized approximation algorithm A for a function f is pseudodeterministic if for every input x there is a unique value v so that A(x) outputs v with high probability, and v is a good approximation of f(x). We show that designing a pseudodeterministic version of Stockmeyer\u27s well known approximation algorithm for the NP-membership counting problem will yield a new circuit lower bound: if such an approximation algorithm exists, then for every k, there is a language in the complexity class ZPP^{NP}_{tt} that does not have n^k-size circuits. While we do not know how to design such an algorithm for the NP-membership counting problem, we show a general result that any randomized approximation algorithm for a counting problem can be transformed to an approximation algorithm that has a constant number of influential random bits. That is, for most settings of these influential bits, the approximation algorithm will be pseudodeterministic