John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo

Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE.

more >>>Xiaoyang Gu

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>>

Philippe Moser

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families,

that get rid of some drawbacks of previous measure notions:

martingale families can make money on all strings,

and yield random sequences with an equal frequency of 0's and 1's.

As applications to F-measure,

more >>>

Philippe Moser

We refine the genericity concept of Ambos-Spies et al, by assigning a real number in $[0,1]$ to every generic set, called its generic density.

We construct sets of generic density any E-computable real in $[0,1]$.

We also introduce strong generic density, and show that it is related to packing ...
more >>>

Xiaoyang Gu, Jack H. Lutz

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 >>>

Maria Lopez-Valdes

This paper describes the Lempel-Ziv dimension (Hausdorff like

dimension inspired in the LZ78 parsing), its fundamental properties

and relation with Hausdorff dimension.

It is shown that in the case of individual infinite sequences, the

Lempel-Ziv dimension matches with the asymptotical Lempel-Ziv

compression ratio.

This fact is used to describe results ... more >>>