We show that hitting sets can derandomize any BPP-algorithm. This gives a positive answer to a fundamental open question in probabilistic algorithms. More precisely, we present a polynomial time deterministic algorithm which uses any given hitting set to approximate the fractions of 1's in the output of any boolean circuit ... more >>>

We use the assumption that all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms to derive collapse consequences for MA, AM, and various subclasses of P/poly. As a further consequence we show for C in {P(PP), PSPACE} that C is not tractable in the ... more >>>

We consider a class, denoted APP, of real-valued functions f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to within any epsilon>0, by a probabilistic Turing machine running in time poly(n,1/epsilon). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete ... more >>>