All reports by Author Jack H. Lutz:

__
TR15-140
| 26th August 2015
__

Adam Case, Jack H. Lutz, Donald Stull#### Reachability Problems for Continuous Chemical Reaction Networks

__
TR14-133
| 15th October 2014
__

Adam Case, Jack H. Lutz#### Mutual Dimension

__
TR14-015
| 24th January 2014
__

Jack H. Lutz, Neil Lutz#### Lines Missing Every Random Point

Revisions: 1

__
TR13-161
| 23rd October 2013
__

Jack H. Lutz#### The Frequent Paucity of Trivial Strings

Revisions: 1

__
TR10-032
| 19th January 2010
__

Jack H. Lutz, Brad Shutters#### Approximate Self-Assembly of the Sierpinski Triangle

__
TR09-022
| 16th February 2009
__

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

Revisions: 1

__
TR08-106
| 12th November 2008
__

Jack H. Lutz#### A Divergence Formula for Randomness and Dimension

__
TR08-037
| 29th February 2008
__

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

Revisions: 1

__
TR08-035
| 18th February 2008
__

James I. Lathrop, Jack H. Lutz, Scott M. Summers#### Strict Self-Assembly of Discrete Sierpinski Triangles

__
TR08-031
| 14th January 2008
__

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers#### Computability and Complexity in Self-Assembly

__
TR06-038
| 10th February 2006
__

David Doty, Jack H. Lutz, Satyadev Nandakumar#### Finite-State Dimension and Real Arithmetic

__
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-079
| 30th August 2004
__

John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn#### The Arithmetical Complexity of Dimension and Randomness

Adam Case, Jack H. Lutz, Donald Stull

Chemical reaction networks (CRNs) model the behavior of molecules in a well-mixed system. The emerging field of molecular programming uses CRNs not only as a descriptive tool, but as a programming language for chemical computation. Recently, Chen, Doty and Soloveichik introduced a new model of chemical kinetics, rate-independent continuous CRNs ... more >>>

Adam Case, Jack H. Lutz

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... more >>>

Jack H. Lutz, Neil Lutz

This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0.

more >>>Jack H. Lutz

A 1976 theorem of Chaitin, strengthening a 1969 theorem of Meyer,says that infinitely many lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. ... more >>>

Jack H. Lutz, Brad Shutters

The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex (typically aperiodic) DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in ... more >>>

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

Jack H. Lutz

If $S$ is an infinite sequence over a finite alphabet $\Sigma$ and $\beta$ is a probability measure on $\Sigma$, then the {\it dimension} of $ S$ with respect to $\beta$, written $\dim^\beta(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $\beta$ is ... 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 >>>

James I. Lathrop, Jack H. Lutz, Scott M. Summers

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely ... more >>>

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

This paper explores the impact of geometry on computability =

and complexity in

Winfree's model of nanoscale self-assembly. We work in the =

two-dimensional

tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =

first

main theorem says that there is a roughly quadratic function f ...
more >>>

David Doty, Jack H. Lutz, Satyadev Nandakumar

We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+alpha, and q*alpha all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives ... 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 >>>

John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn

Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].

Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... more >>>