All reports by Author Elvira Mayordomo:

__
TR09-022
| 16th February 2009
__

Jack H. Lutz, Elvira Mayordomo#### Inseparability and Strong Hypotheses for Disjoint NP Pairs

Revisions: 1

__
TR08-037
| 29th February 2008
__

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo#### Curves That Must Be Retraced

Revisions: 1

__
TR07-051
| 18th April 2007
__

Pilar Albert, Elvira Mayordomo, Philippe Moser#### Bounded Pushdown dimension vs Lempel Ziv information density

__
TR05-157
| 10th December 2005
__

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo#### Points on Computable Curves

__
TR04-029
| 7th April 2004
__

John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo#### Scaled dimension and the Kolmogorov complexity of Turing hard sets

__
TR01-059
| 20th July 2001
__

Elvira Mayordomo#### A Kolmogorov complexity characterization of constructive Hausdorff dimension

Revisions: 3

Jack H. Lutz, Elvira Mayordomo

This paper investigates the existence of inseparable disjoint

pairs of NP languages and related strong hypotheses in

computational complexity. Our main theorem says that, if NP does

not have measure 0 in EXP, then there exist disjoint pairs of NP

languages that are P-inseparable, in fact TIME(2^(n^k)-inseparable.

We also relate ...
more >>>

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f ... more >>>

Pilar Albert, Elvira Mayordomo, Philippe Moser

In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol ... more >>>

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

The ``analyst's traveling salesman theorem'' of geometric

measure theory characterizes those subsets of Euclidean

space that are contained in curves of finite length.

This result, proven for the plane by Jones (1990) and

extended to higher-dimensional Euclidean spaces by

Okikiolu (1991), says that a bounded set $K$ is contained

more >>>

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

We obtain the following full characterization of constructive dimension

in terms of algorithmic information content. For every sequence A,

cdim(A)=liminf_n (K(A[0..n-1])/n.