Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Resource-bounded dimension:
TR04-029 | 7th April 2004
John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo

Scaled dimension and the Kolmogorov complexity of Turing hard sets

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

TR04-047 | 22nd April 2004
Xiaoyang Gu

A note on dimensions of polynomial size circuits

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

TR05-045 | 12th April 2005
Philippe Moser

Martingale Families and Dimension in P

Revisions: 1

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

TR05-060 | 30th May 2005
Philippe Moser

Generic Density and Small Span Theorem

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

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

TR06-077 | 12th June 2006
Maria Lopez-Valdes

Lempel-Ziv Dimension for Lempel-Ziv Compression

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

ISSN 1433-8092 | Imprint