Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ALMOST CLASSES:
Reports tagged with almost classes:
TR05-160 | 10th December 2005
Xiaoyang Gu, Jack H. Lutz

Dimension Characterizations of Complexity Classes

We use derandomization to show that sequences of positive \pspace-dimension -- in fact, even positive \Delta^\p_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 \Delta^p_3-dimension is positive, then \BPP\subseteq \P^S and, moreover, ... more >>>




ISSN 1433-8092 | Imprint