Dimension Characterizations of Complexity Classes

We use derandomization to show that sequences of positive pspace-dimension -- in fact, even positive # k -dimension for suitable k -- have, for many purposes, the full power of random oracles. For example, we show that, if S is any binary sequence whose # 3 -dimension is positive, then and, moreover, every BPP promise problem is P -separable. We prove analogous results at higher levels of the polynomial-time hierarchy. The dimension-almost-class of a complexity class denoted by dimalmost-C, is the class consisting of all problems A such that A for all but a Hausdor# dimension 0 set of oracles S. Our results yield several characterizations of complexity classes, such as BPP = dimalmost-P and AM = dimalmost-NP, that refine previously known results on almost-classes. They also yield results, such as Promise-BPP = almost-P-Sep = dimalmost-P-Sep, in which even the almost-class appears to be a new characterization