All reports by Author Xiaoyang Gu:

__
TR08-037
| 29th February 2008
__

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

Revisions: 1

__
TR05-160
| 10th December 2005
__

Xiaoyang Gu, Jack H. Lutz#### Dimension Characterizations of Complexity Classes

__
TR05-157
| 10th December 2005
__

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

__
TR05-089
| 30th July 2005
__

Xiaoyang Gu, Jack H. Lutz, Philippe Moser#### Dimensions of Copeland-Erdos Sequences

__
TR04-047
| 22nd April 2004
__

Xiaoyang Gu#### A note on dimensions of polynomial size circuits

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

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

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

Xiaoyang Gu, Jack H. Lutz, Philippe Moser

The base-$k$ {\em Copeland-Erd\"os sequence} given by an infinite

set $A$ of positive integers is the infinite

sequence $\CE_k(A)$ formed by concatenating the base-$k$

representations of the elements of $A$ in numerical

order. This paper concerns the following four

quantities.

\begin{enumerate}[$\bullet$]

\item

The {\em finite-state dimension} $\dimfs (\CE_k(A))$,

a finite-state ...
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 >>>