Publications
Research Papers

Jack H. Lutz and Neil Lutz,
Algorithmic information, plane Kakeya sets, and conditional dimension,
ACM Transactions on Computation Theory 10 (2018), article 7 (22 pages).

Adam Case, Jack H. Lutz, and D. M. Stull,
Reachability problems for continuous chemical reaction networks,
Natural Computing 17 (2018), pp. 223230.

Adam Case and Jack H. Lutz,
Mutual dimension and random sequences,
Theoretical Computer Science 731 (2018), pp. 6887.

Xiang Huang, Titus H. Klinge, James I. Lathrop, Xiaoyuan Li, and Jack H. Lutz,
Realtime computability of real numbers by chemical reaction networks,
Proceedings of the Sixteenth International Conference on Unconventional
Computation and Natural Computation(UCNC 2017, Fayetteville, AR, June 59, 2017),
Springer, 2017, pp. 2940.

Samuel J. Ellis, Titus H. Klinge, James I. Lathrop, Jack H. Lutz, Robyn R. Lutz, and Andrew S. Miner,
Runtime fault detection in programmed molecular systems,
submitted.

Jack H. Lutz and Elvira Mayordomo,
Computing absolutely normal numbers in nearly linear time,
submitted.

Titus H. Klinge, James I. Lathrop, and Jack H. Lutz,
Robust biomolecular finite automata,
Technical Report 1505.03931, arXiv ePrint archive, 2015.

Jack H. Lutz and Neil Lutz, Lines missing every random point,
Computability 4 (2015), pp. 85102.

Adam Case and Jack H. Lutz, Mutual dimension, ACM Transactions on Computation
Theory 7 (2015), article 12 (26 pages).

Samuel J. Ellis, Eric R. Henderson, Titus H. Klinge, James I. Lathrop, Jack H. Lutz, Robyn R. Lutz,
Divita Mathur, and Andrew S. Miner,
Automated requirements analysis for a molecular watchdog timer,
Proceedings of the Twentyninth IEEE/ACM International Conference on Automated Software Engineering
(ASE 2014, Vasteras, Sweden, September 1519, 2014), pp. 767778. Paper received the IFIP TC2 Manfred Paul Award
for Excellence in Software: Theory and Practice.

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser,
Dimension spectra of random subfractals of selfsimilar
fractals,
Annals of Pure and Applied Logic 165 (2014), pp. 17071726.

Randall Dougherty, Jack H. Lutz, R. Daniel Mauldin, and Jason Teutsch,
Translating the Cantor set by a random real,
Transactions of the American Mathematical Society 366 (2014), pp. 30273041.

Jack H. Lutz, The frequent paucity of trivial strings,
Information Processing Letters 114 (2014), pp. 643645.

David S. Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien
Woods, The tile assembly model is intrinsically universal,
Proceedings of the Fiftythird Annual IEEE Symposium on Foundations of Computer Science
(FOCS 2012, New Brunswick, NJ, October 2023, 2012), pp. 302310.

Robyn R. Lutz, Jack H. Lutz, James I. Lathrop, Titus H. Klinge, Divita Mathur, D.
M. Stull, Taylor G. Bergquist, and Eric R. Henderson,
Requirements analysis for a product family of DNA nanodevices, Proceedings of
the Twentieth IEEE International Requirements Engineering Conference (RE 2012,
Chicago, IL, September 2428, 2012), pp. 211220.

Jack H. Lutz and Brad Shutters,
Approximate selfassembly of the Sierpinski triangle,
Theory of Computing Systems 51 (2012), pp. 372400.

Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo,
Inseparability and strong hypotheses for disjoint NP pairs,
Theory of Computing Systems 51 (2012), pp. 229247.

Robyn Lutz, Jack Lutz, James Lathrop, Titus Klinge, Eric Henderson, Divita Mathur, and Dalia Abo Sheasha,
Engineering and verifying requirements for programmable selfassembling
nanomachines, Proceedings of the ThirtyFourth International Conference on Software Engineering
(ICSE 2012, Zurich, Switzerland, June 29, 2012), pp. 13611364.

Xiaoyang Gu and Jack H. Lutz,
Effective dimensions and relative frequencies,
Theoretical Computer Science 412 (2011), pp. 66966711.

Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo,
Curves that must be retraced,
Information and Computation 209 (2011), pp. 9921006.

Xiaoyang Gu, Jack H. Lutz, Satyadev Nandakumar, and James S. Royer,
Axiomatizing resource bounds for measure,
Models of Computation in Context: Proceedings of the Seventh Conference
on Computability in Europe (CiE 2011, Sofia, Bulgaria, June 27July 2,
2011), Springer, 2011, pp. 102111.

James I. Lathrop, Jack H. Lutz, and Brian Patterson,
Multiresolution cellular automata for real computation,
Models of Computation in Context: Proceedings of the Seventh Conference
on Computability in Europe (CiE 2011, Sofia, Bulgaria, June 27July 2,
2011), Springer, 2011, pp. 181190.

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers,
Computability and complexity in selfassembly,
Theory of Computing Systems 48 (2011), pp. 617647.

Jack H. Lutz,
A divergence formula for randomness and dimension,
Theoretical Computer Science 412 (2011), pp. 166177.

David S. Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods,
Intrinsic universality in selfassembly,
Proceedings of the TwentySeventh International Symposium on Theoretical Aspects of
Computer Science (STACS 2010, Nancy, France, March 46, 2010), pp. 275286.

David S. Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods,
Random number selection in selfassembly,
Proceedings of the Eighth International Conference on Unconventional Computation
(UC 2009, Ponta Delgada, Portugal, September 711, 2009), Springer, pp. 143157.

James I. Lathrop, Jack H. Lutz, and Scott M. Summers,
Strict selfassembly of discrete Sierpinski triangles,
Theoretical Computer Science, 410 (2009), pp. 384405.

Xiaoyang Gu and Jack H. Lutz,
Dimension characterizations of complexity classes,
Computational Complexity
17 (2008), pp. 459474.

Jack H. Lutz and Elvira Mayordomo,
Dimensions of points in selfsimilar fractals,
SIAM Journal on Computing, 38 (2008), pp. 10801112..

Jack H. Lutz and Klaus Weihrauch,
Connectivity properties of dimension level sets,
Mathematical Logic Quarterly, 54 (2008), pp. 483491.

Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo,
Points on computable curves,
Proceedings of the FortySeventh Annual IEEE Symposium on Foundations
of Computer Science (FOCS 2006, Berkeley, CA, October 2224, 2006),
IEEE Computer Society Press, 2006, pp. 469474.

David Doty, Jack H. Lutz, and Satyadev Nandakumar,
Finitestate dimension and real arithmetic,
Information and Computation
205 (2007), pp. 16401651.

Xiaoyang Gu, Jack H. Lutz, and Philippe Moser,
Dimensions of CopelandErdös sequences,
Information and Computation
205 (2007), pp. 13171333.

Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo,
Effective strong dimension in algorithmic information and computational complexity,
SIAM Journal on Computing
37 (2007), pp. 671705.

John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn,
The arithmetical complexity of dimension and randomness,
ACM Transactions on Computational Logic
8 (2007), article no. 13.

Dave Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser,
Zetadimension,
Proceedings of the Thirtieth International
Symposium on Mathematical Foundations of Computer Science (MFCS 2005, Gdansk,
Poland, August 29  September 2, 2005), SpringerVerlag, 2005, pp. 283294.

John M. Hitchcock and Jack H. Lutz,
Why computational complexity requires stricter martingales,
Theory of Computing Systems
39 (2006), pp. 277296.
 Lance Fortnow and Jack H. Lutz,
Prediction and dimension,
Journal of Computer and System Sciences
70 (2005), pp. 570589.

Stephen A. Fenner, Jack H. Lutz, Elvira Mayordomo, and Patrick Reardon,
Weakly useful sequences,
Information and Computation
197 (2005), pp. 4154.

Jack H. Lutz,
Computability versus exact computability of martingales,
Information Processing Letters
92 (2004), pp. 235237.
 John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo,
Scaled dimension and nonuniform complexity,
Journal of
Computer and System Sciences 69 (2004), pp. 97122.
 Jack J. Dai, James I. Lathrop, Jack H. Lutz, and Elvira Mayordomo,
Finitestate dimension,
Theoretical Computer Science 310 (2004), pp. 133.
 Josef M. Breutzmann, David W. Juedes, and Jack H. Lutz,
Baire category and nowhere differentiability for feasible real functions,
Mathematical Logic Quarterly
50 (2004), pp. 460472.
 Jack H. Lutz,
The dimensions of individual strings and sequences,
Information and Computation 187 (2003), pp. 4979.
 Jack H. Lutz,
Dimension in complexity classes,
SIAM Journal on
Computing 32 (2003), pp. 12361259.
 Jack H. Lutz,
Gales and the constructive dimension of individual sequences,
Proceedings of the TwentySeventh
International Colloquium on Automata, Languages, and
Programming (ICALP 2000, Geneva, Switzerland, July 915, 2000),
SpringerVerlag, 2000, pp. 902913.
 Jack H. Lutz, Vikram Mhetre, and Sridhar Srinivasan,
Hard instances of hard problems,
Proceedings of the Seventeenth Symposium on Theoretical Aspects of
Computer Science (STACS 2000, Lille, France, February 1719, 2000),
SpringerVerlag, 2000, pp. 324333.
 Jack H. Lutz and Martin Strauss,
Bias invariance of small upper spans,
Proceedings of the Seventeenth Symposium on Theoretical Aspects of
Computer Science (STACS 2000, Lille, France, February 1719, 2000),
SpringerVerlag, 2000, pp. 7486.
 Jack J. Dai and Jack H. Lutz,
Query order and NPcompleteness,
Proceedings of the Fourteenth Annual IEEE Conference on
Computational Complexity (CCC 1999, Atlanta, GA, May 46, 1999), IEEE
Computer Society Press, 1999, pp. 142148.
 David W. Juedes and Jack H. Lutz,
Modeling timebounded prefix Kolmogorov complexity,
Theory of Computing Systems 33 (2000), pp. 111123.
 Jack H. Lutz,
Resourcebounded measure,
Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity
(CCC 1998, Buffalo, NY, June 1518, 1998), IEEE Computer Society Press,
1998, pp. 236248.
 Jack H. Lutz and Yong Zhao,
The density of weakly complete problems under adaptive reductions,
SIAM Journal on Computing 30 (2000), pp. 11971210.
 Josef M. Breutzmann and Jack H. Lutz,
Equivalence of measures of complexity classes,
SIAM Journal on Computing 29 (2000), pp. 302326.
 James I. Lathrop and Jack H. Lutz,
Recursive computational depth,
Information and Computation
153 (1999), pp. 139172.
 Jack H. Lutz and David L. Schweizer,
Feasible reductions to KolmogorovLoveland stochastic sequences,
Theoretical Computer Science
225 (1999), pp. 185194.
 Jack H. Lutz,
Oneway functions and balanced NP,
manuscript.
 Amy K. Lorentz and Jack H. Lutz,
Genericity and randomness over feasible probability measures,
Theoretical Computer Science
207 (1998), pp. 245259.
 Jack H. Lutz,
Observations on measure and lowness for Δ_{2}P,
Theory of Computing Systems 30 (1997), pp. 429442.
 Jack H. Lutz and Elvira Mayordomo,
Cook versus Karp/Levin: separating completeness notions if NP is not small,
Theoretical Computer Science 164 (1996), pp. 141163.
 David W. Juedes and Jack H. Lutz,
Completeness and weak completeness under
polynomialsize circuits,
Information
and Computation 125 (1996), pp. 1331.
 Jack H. Lutz,
Weakly hard problems,
SIAM Journal on Computing 24 (1995), pp. 11701189.
 Ronald V. Book, Jack H. Lutz and David M. Martin, Jr.,
The global power of additional queries to random oracles,
Information and Computation 120 (1995), pp. 4954.
 David W. Juedes and Jack H. Lutz,
Weak completeness in E and E_{2},
Theoretical Computer Science 143 (1995),
pp. 149158.
 David W. Juedes and Jack H. Lutz,
The complexity and distribution of hard problems,
SIAM Journal on Computing 24
(1995), pp. 279295.
 Jack H. Lutz,
A small span theorem for P/PolyTuring reductions,
Proceedings of the Tenth Annual Structure in Complexity
Theory Conference (CCC 1995, Minneapolis,
MN, June 1922, 1995), IEEE Computer Society Press, 1995, pp. 324330.
 David W. Juedes, James I. Lathrop, and Jack H. Lutz,
Computational depth and reducibility,
Theoretical Computer Science 132 (1994), pp. 3770.
 Jack H. Lutz and Elvira Mayordomo,
Measure, stochasticity, and the density of hard languages,
SIAM Journal on Computing 23 (1994), pp. 762779.
 Ronald V. Book, Jack H. Lutz, and Klaus W. Wagner,
An observation on probability versus randomness with
applications to complexity classes,
Mathematical Systems Theory 27 (1994), pp. 201209.
 Jack H. Lutz,
A pseudorandom oracle characterization of BPP,
SIAM Journal on Computing 22 (1993), pp. 10751086.
 Ronald V. Book and Jack H. Lutz,
On languages with very high spacebounded Kolmogorov complexity,
SIAM Journal on Computing
22 (1993), pp. 395402.
 Jack H. Lutz and William J. Schmidt,
Circuit size relative to pseudorandom oracles,
Theoretical Computer Science 107
(1993), pp. 95120.
 David W. Juedes and Jack H. Lutz,
Kolmogorov complexity, complexity cores, and the
distribution of hardness,
in O. Watanabe (ed.), Kolmogorov Complexity and Computational
Complexity, SpringerVerlag, 1992, pp. 4365.
 Jack H. Lutz,
Almost everywhere high nonuniform complexity,
Journal of Computer and System Sciences 44 (1992), pp. 220258.
 Jack H. Lutz,
On independent random oracles,
Theoretical Computer Science, 92 (1992), pp. 301307.
 Jack H. Lutz,
An upward measure separation theorem,
Theoretical Computer Science 81 (1991), pp. 127135.
 Jack H. Lutz,
Pseudorandom sources for BPP,
Journal of Computer and System Sciences 41 (1990),
pp. 307320.
 Jack H. Lutz, Category and measure in complexity classes,
SIAM Journal on Computing 19 (1990), pp. 11001131.
Survey Papers
 John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo,
The fractal
geometry of complexity classes, in the Complexity Theory Column
(L.A. Hemaspaandra, ed.),
SIGACT News 36 (2005), pp. 2438.

Jack H. Lutz,
Effective fractal dimensions (invited lecture
at the International Conference on Computability and Complexity
in Analysis, Cincinnati, OH, August 2830, 2003),
Mathematical Logic Quarterly 51 (2005), pp. 6272.

Jack H. Lutz and Elvira Mayordomo,
Twelve problems in resourcebounded measure,
in the Computational Complexity Column (E. Allender, ed.),
Bulletin of the European Association for Theoretical Computer Science
68 (1999), pp. 6480, and in
G. Paun, G. Rozenberg, and A. Salomaa (eds.),
Current Trends in Theoretical Computer Science: Entering the 21st Century,
World Scientific, 2001, pp. 83101.
 And then there were eight:
Updates on the status of these twelve problems.

Jack H. Lutz,
The quantitative structure of exponential time,
in L. A. Hemaspaandra and A. L. Selman (eds.), Complexity Theory
Retrospective II, SpringerVerlag, 1997, pp. 225254.