5 papers
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…
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…