11 citations · 16 across the 10 of their papers we have counts for
18 papers
Lines in Every Direction with No ee-Random Points
Neil Lutz, Spencer Park Martin, Rain White
We prove that in every direction in the Euclidean plane, there exists a line containing no double exponential time random (ee-random) points. This means each point on these lines h…
Dimension and the Structure of Complexity Classes
Jack H. Lutz, Neil Lutz, Elvira Mayordomo
We prove three results on the dimension structure of complexity classes. 1. The Point-to-Set Principle, which has recently been used to prove several new theorems in fractal geomet…
Algorithmically Optimal Outer Measures
Jack H. Lutz, Neil Lutz
We investigate the relationship between algorithmic fractal dimensions and the classical local fractal dimensions of outer measures in Euclidean spaces. We introduce global and loc…
Extending the Reach of the Point-to-Set Principle
Jack H. Lutz, Neil Lutz, Elvira Mayordomo
The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces…
Who Asked Us? How the Theory of Computing Answers Questions about Analysis
Jack H. Lutz, Neil Lutz
Algorithmic fractal dimensions -- constructs of computability theory -- have recently been used to answer open questions in classical geometric measure theory, questions of mathema…
A Center in Your Neighborhood: Fairness in Facility Location
Christopher Jung, Sampath Kannan, Neil Lutz
When selecting locations for a set of facilities, standard clustering algorithms may place unfair burden on some individuals and neighborhoods. We formulate a fairness concept that…
Robustness and Games Against Nature in Molecular Programming
Jack H. Lutz, Neil Lutz, Robyn R. Lutz +1
Matter, especially DNA, is now programmed to carry out useful processes at the nanoscale. As these programs and processes become more complex and their envisioned safety-critical a…
Quantifying the Burden of Exploration and the Unfairness of Free Riding
Christopher Jung, Sampath Kannan, Neil Lutz
We consider the multi-armed bandit setting with a twist. Rather than having just one decision maker deciding which arm to pull in each round, we have different decision makers…
Projection Theorems Using Effective Dimension
Neil Lutz, D. M. Stull
In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theo…
Dimension Spectra of Lines
Neil Lutz, D. M. Stull
This paper investigates the algorithmic dimension spectra of lines in the Euclidean plane. Given any line L with slope a and vertical intercept b, the dimension spectrum sp(L) is t…
A Note on Pointwise Dimensions
Neil Lutz
This short note describes a connection between algorithmic dimensions of individual points and classical pointwise dimensions of measures.
Fractal Intersections and Products via Algorithmic Dimension
Neil Lutz
Algorithmic fractal dimensions quantify the algorithmic information density of individual points and may be defined in terms of Kolmogorov complexity. This work uses these dimensio…
Bounding the Dimension of Points on a Line
Neil Lutz, D. M. Stull
We use Kolmogorov complexity methods to give a lower bound on the effective Hausdorff dimension of the point (x, ax+b), given real numbers a, b, and x. We apply our main theorem to…
Stateless Computation
Danny Dolev, Michael Erdmann, Neil Lutz +2
We present and explore a model of stateless and self-stabilizing distributed computation, inspired by real-world applications such as routing on today's Internet. Processors in our…
Algorithmic information, plane Kakeya sets, and conditional dimension
Jack H. Lutz, Neil Lutz
We formulate the conditional Kolmogorov complexity of x given y at precision r, where x and y are points in Euclidean spaces and r is a natural number. We demonstrate the utility o…
Dynamics at the Boundary of Game Theory and Distributed Computing
Aaron D. Jaggard, Neil Lutz, Michael Schapira +1
We use ideas from distributed computing and game theory to study dynamic and decentralized environments in which computational nodes, or decision makers, interact strategically and…
Self-stabilizing uncoupled dynamics
Aaron D. Jaggard, Neil Lutz, Michael Schapira +1
Dynamics in a distributed system are self-stabilizing if they are guaranteed to reach a stable state regardless of how the system is initialized. Game dynamics are uncoupled if eac…
Lines Missing Every Random Point
Jack H. Lutz, Neil Lutz
We prove that there is, in every direction in Euclidean space, a line that misses every computably random point. We also prove that there exist, in every direction in Euclidean spa…