Publications

Processing math: 0%

$\newcommand{\n}{\hat{n}}\newcommand{\thetai}{\theta_\mathrm{i}}\newcommand{\thetao}{\theta_\mathrm{o}}\newcommand{\d}[1]{\mathrm{d}#1}\newcommand{\w}{\hat{\omega}}\newcommand{\wi}{\w_\mathrm{i}}\newcommand{\wo}{\w_\mathrm{o}}\newcommand{\wh}{\w_\mathrm{h}}\newcommand{\Li}{L_\mathrm{i}}\newcommand{\Lo}{L_\mathrm{o}}\newcommand{\Le}{L_\mathrm{e}}\newcommand{\Lr}{L_\mathrm{r}}\newcommand{\Lt}{L_\mathrm{t}}\newcommand{\O}{\mathrm{O}}\newcommand{\degrees}{{^{\large\circ}}}\newcommand{\T}{\mathsf{T}}\newcommand{\mathset}[1]{\mathbb{#1}}\newcommand{\Real}{\mathset{R}}\newcommand{\Integer}{\mathset{Z}}\newcommand{\Boolean}{\mathset{B}}\newcommand{\Complex}{\mathset{C}}\newcommand{\un}[1]{\,\mathrm{#1}}$

Publications

Recent Survey Papers

Jack H. Lutz and Robyn R. Lutz, Reasoning As If, in Nataša Jonoska and Erik Winfree (eds.), Visions of DNA Nanotechnology at 40 for the Next 40: A Tribute to Nadrian C. Seeman, pp. 271-278, Springer 2023.
Jack H. Lutz and Elvira Mayordomo, Algorithmic fractal dimensions in geometric measure theory, in Vasco Brattka and Peter Hertling (eds.), Handbook of Computability and Complexity in Analysis, pp. 271-302, Springer, 2021.
Jack H. Lutz and Neil Lutz, Who asked us? How the theory of computing answers questions about analysis, Ding-Zhu Du and Jie Wang (eds.), Complexity and Approximation: In Memory of Ker-I Ko, pp. 48-56, Springer, 2020.

Research Papers

Jack H. Lutz, Hausdorff dimensions of solutions of Cauchy's functional equation, submitted.
Jack H. Lutz and Neil Lutz, Algorithmically optimal outer measures, submitted.
Jack H. Lutz and Andrei Migunov, Algorithmic dimensions via learning functions, Proceedings of the Forty-ninth International Symposium on Mathematical Foundations of Computer Science (MFCS 2024, Bratislava, Slovakia, August 26-30, 2024), pp. 72:1-72:13.
James I. Lathrop, Jack H. Lutz, Robyn R. Lutz, Hugh D. Potter, and Matthew R. Riley, Population-induced phase transitions and the verification of chemical reaction networks, Natural Computing, 23 (2024), pp. 347-363.
Jack H. Lutz, Renrui Qi, and Liang Yu, The Point-to-Set Principle and the dimensions of Hamel bases, Computability 13 (2024), pp. 105-112.
Jack H. Lutz, Neil Lutz, and Elvira Mayordomo, Extending the reach of the point-to-set principle, Information and Computation 294 (2023), Article 105078 (19 pages).
Jack H. Lutz, Satyadev Nandakumar, and Subin Pulari, A Weyl criterion for finite-state dimension and applications, Proceedings of the Forty-eighth International Symposium on Mathematical Foundations of Computer Science (MFCS 2023, Bordeaux, France, August 28-September 1, 2023), pp. 65:1-65:16.
Jack H. Lutz, Neil Lutz, and Elvira Mayordomo, Dimension and the structure of complexity classes, Theory of Computing Systems 67 (2023), pp. 473-490.
Adam Case and Jack H. Lutz, Finite-state mutual dimension, Proceedings of the Fifty-eighth Annual Allerton Conference on Communication, Control, and Computing (Allerton 2022, Monticello, IL, September 28-30, 2022), IEEE, 2022 (8 pages).
Jack H. Lutz and Elvira Mayordomo, Computing absolutely normal numbers in nearly linear time, Information and Computation 281 (2021), article 104746 (12 pages).
Xiang Huang, Jack H. Lutz, Elvira Mayordomo, and Donald M. Stull, Asymptotic divergences and strong dichotomy, IEEE Transactions on Information Theory 67 (2021), pp. 6296-6305.
Titus H. Klinge, James I. Lathrop, and Jack H. Lutz, Robust biomolecular finite automata, Theoretical Computer Science 816 (2020), pp. 114-143.
Xiang Huang, Jack H. Lutz, and Andrei N. Migunov, Algorithmic randomness in continuous-time Markov chains, Proceedings of the Fifty-seventh Annual Allerton Conference on Communication, Control, and Computing (Allerton 2019, Monticello, IL, September 24-27, 2019), pp. 615-622.
Jack H. Lutz, Neil Lutz, Robyn R. Lutz, and Matthew R. Riley, Robustness and games against nature in molecular programming, Proceedings of the IEEE/ACM Forty-first International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER 2019, Montreal, Canada, May 25-31, 2019), pp. 65-68.
Samuel J. Ellis, Titus H. Klinge, James I. Lathrop, Jack H. Lutz, Robyn R. Lutz, Andrew S. Miner, and Hugh D. Potter, Runtime fault detection in programmed molecular systems, ACM Transactions on Software Engineering and Methodology 28 (2019), Article 6 (20 pages).
Xiang Huang, Titus H. Klinge, James I. Lathrop, Xiaoyuan Li, and Jack H. Lutz, Real-time computability of real numbers by chemical reaction networks, Natural Computing 18 (2019), pp. 63-73.
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. 223-230.
Adam Case and Jack H. Lutz, Mutual dimension and random sequences, Theoretical Computer Science 731 (2018), pp. 68-87.
Jack H. Lutz and Neil Lutz, Lines missing every random point, Computability 4 (2015), pp. 85-102.
Adam Case and Jack H. Lutz, Mutual dimension, ACM Transactions on Computation Theory 7 (2015), article 12 (26 pages).
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser, Dimension spectra of random subfractals of self-similar fractals, Annals of Pure and Applied Logic 165 (2014), pp. 1707-1726.
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. 3027-3041.
Jack H. Lutz, The frequent paucity of trivial strings, Information Processing Letters 114 (2014), pp. 643-645.
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 Fifty-third Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012, New Brunswick, NJ, October 20-23, 2012), pp. 302-310.
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 24-28, 2012), pp. 211-220.
Jack H. Lutz and Brad Shutters, Approximate self-assembly of the Sierpinski triangle, Theory of Computing Systems 51 (2012), pp. 372-400.
Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo, Inseparability and strong hypotheses for disjoint NP pairs, Theory of Computing Systems 51 (2012), pp. 229-247.
Robyn Lutz, Jack Lutz, James Lathrop, Titus Klinge, Eric Henderson, Divita Mathur, and Dalia Abo Sheasha, Engineering and verifying requirements for programmable self-assembling nanomachines, Proceedings of the Thirty-Fourth International Conference on Software Engineering (ICSE 2012, Zurich, Switzerland, June 2-9, 2012), pp. 1361-1364.
Xiaoyang Gu and Jack H. Lutz, Effective dimensions and relative frequencies, Theoretical Computer Science 412 (2011), pp. 6696-6711.
Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo, Curves that must be retraced, Information and Computation 209 (2011), pp. 992-1006.
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 27-July 2, 2011), Springer, 2011, pp. 102-111.
James I. Lathrop, Jack H. Lutz, and Brian Patterson, Multi-resolution cellular automata for real computation, Models of Computation in Context: Proceedings of the Seventh Conference on Computability in Europe (CiE 2011, Sofia, Bulgaria, June 27-July 2, 2011), Springer, 2011, pp. 181-190.
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers, Computability and complexity in self-assembly, Theory of Computing Systems 48 (2011), pp. 617-647.
Jack H. Lutz, A divergence formula for randomness and dimension, Theoretical Computer Science 412 (2011), pp. 166-177.
David S. Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods, Intrinsic universality in self-assembly, Proceedings of the Twenty-Seventh International Symposium on Theoretical Aspects of Computer Science (STACS 2010, Nancy, France, March 4-6, 2010), pp. 275-286.
David S. Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods, Random number selection in self-assembly, Proceedings of the Eighth International Conference on Unconventional Computation (UC 2009, Ponta Delgada, Portugal, September 7-11, 2009), Springer, pp. 143-157.
James I. Lathrop, Jack H. Lutz, and Scott M. Summers, Strict self-assembly of discrete Sierpinski triangles, Theoretical Computer Science, 410 (2009), pp. 384-405.
Xiaoyang Gu and Jack H. Lutz, Dimension characterizations of complexity classes, Computational Complexity 17 (2008), pp. 459-474.
Jack H. Lutz and Elvira Mayordomo, Dimensions of points in self-similar fractals, SIAM Journal on Computing, 38 (2008), pp. 1080-1112.
Jack H. Lutz and Klaus Weihrauch, Connectivity properties of dimension level sets, Mathematical Logic Quarterly, 54 (2008), pp. 483-491.
Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo, Points on computable curves, Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006, Berkeley, CA, October 22-24, 2006), IEEE Computer Society Press, 2006, pp. 469-474.
David Doty, Jack H. Lutz, and Satyadev Nandakumar, Finite-state dimension and real arithmetic, Information and Computation 205 (2007), pp. 1640-1651.
Xiaoyang Gu, Jack H. Lutz, and Philippe Moser, Dimensions of Copeland-Erdös sequences, Information and Computation 205 (2007), pp. 1317-1333.
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. 671-705.
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, Zeta-dimension, Proceedings of the Thirtieth International Symposium on Mathematical Foundations of Computer Science (MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005), Springer-Verlag, 2005, pp. 283-294.
John M. Hitchcock and Jack H. Lutz, Why computational complexity requires stricter martingales, Theory of Computing Systems 39 (2006), pp. 277-296.
Lance Fortnow and Jack H. Lutz, Prediction and dimension, Journal of Computer and System Sciences 70 (2005), pp. 570-589.
Stephen A. Fenner, Jack H. Lutz, Elvira Mayordomo, and Patrick Reardon, Weakly useful sequences, Information and Computation 197 (2005), pp. 41-54.
Jack H. Lutz, Computability versus exact computability of martingales, Information Processing Letters 92 (2004), pp. 235-237.
John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo, Scaled dimension and nonuniform complexity, Journal of Computer and System Sciences 69 (2004), pp. 97-122.
Jack J. Dai, James I. Lathrop, Jack H. Lutz, and Elvira Mayordomo, Finite-state dimension, Theoretical Computer Science 310 (2004), pp. 1-33.
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. 460-472.
Jack H. Lutz, The dimensions of individual strings and sequences, Information and Computation 187 (2003), pp. 49-79.
Jack H. Lutz, Dimension in complexity classes, SIAM Journal on Computing 32 (2003), pp. 1236-1259.
Jack H. Lutz, Gales and the constructive dimension of individual sequences, Proceedings of the Twenty-Seventh International Colloquium on Automata, Languages, and Programming (ICALP 2000, Geneva, Switzerland, July 9-15, 2000), Springer-Verlag, 2000, pp. 902-913.
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 17-19, 2000), Springer-Verlag, 2000, pp. 324-333.
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 17-19, 2000), Springer-Verlag, 2000, pp. 74-86.
Jack J. Dai and Jack H. Lutz, Query order and NP-completeness, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (CCC 1999, Atlanta, GA, May 4-6, 1999), IEEE Computer Society Press, 1999, pp. 142-148.
David W. Juedes and Jack H. Lutz, Modeling time-bounded prefix Kolmogorov complexity, Theory of Computing Systems 33 (2000), pp. 111-123.
Jack H. Lutz, Resource-bounded measure, Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity (CCC 1998, Buffalo, NY, June 15-18, 1998), IEEE Computer Society Press, 1998, pp. 236-248.
Jack H. Lutz and Yong Zhao, The density of weakly complete problems under adaptive reductions, SIAM Journal on Computing 30 (2000), pp. 1197-1210.
Josef M. Breutzmann and Jack H. Lutz, Equivalence of measures of complexity classes, SIAM Journal on Computing 29 (2000), pp. 302-326.
James I. Lathrop and Jack H. Lutz, Recursive computational depth, Information and Computation 153 (1999), pp. 139-172.
Jack H. Lutz and David L. Schweizer, Feasible reductions to Kolmogorov-Loveland stochastic sequences, Theoretical Computer Science 225 (1999), pp. 185-194.
Jack H. Lutz, One-way 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. 245-259.
Jack H. Lutz, Observations on measure and lowness for $\Delta_2^\textrm{P}$ , Theory of Computing Systems 30 (1997), pp. 429-442.
Jack H. Lutz and Elvira Mayordomo, Cook versus Karp/Levin: separating completeness notions if NP is not small, Theoretical Computer Science 164 (1996), pp. 141-163.
David W. Juedes and Jack H. Lutz, Completeness and weak completeness under polynomial-size circuits, Information and Computation 125 (1996), pp. 13-31.
Jack H. Lutz, Weakly hard problems, SIAM Journal on Computing 24 (1995), pp. 1170-1189.
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. 49-54.
David W. Juedes and Jack H. Lutz, Weak completeness in E and E₂, Theoretical Computer Science 143 (1995), pp. 149-158.
David W. Juedes and Jack H. Lutz, The complexity and distribution of hard problems, SIAM Journal on Computing 24 (1995), pp. 279-295.
Jack H. Lutz, A small span theorem for P/Poly-Turing reductions, Proceedings of the Tenth Annual Structure in Complexity Theory Conference (CCC 1995, Minneapolis, MN, June 19-22, 1995), IEEE Computer Society Press, 1995, pp. 324-330.
David W. Juedes, James I. Lathrop, and Jack H. Lutz, Computational depth and reducibility, Theoretical Computer Science 132 (1994), pp. 37-70.
Jack H. Lutz and Elvira Mayordomo, Measure, stochasticity, and the density of hard languages, SIAM Journal on Computing 23 (1994), pp. 762-779.
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. 201-209.
Jack H. Lutz, A pseudorandom oracle characterization of BPP, SIAM Journal on Computing 22 (1993), pp. 1075-1086.
Ronald V. Book and Jack H. Lutz, On languages with very high space-bounded Kolmogorov complexity, SIAM Journal on Computing 22 (1993), pp. 395-402.
Jack H. Lutz and William J. Schmidt, Circuit size relative to pseudorandom oracles, Theoretical Computer Science 107 (1993), pp. 95-120.
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, Springer-Verlag, 1992, pp. 43-65.
Jack H. Lutz, Almost everywhere high nonuniform complexity, Journal of Computer and System Sciences 44 (1992), pp. 220-258.
Jack H. Lutz, On independent random oracles, Theoretical Computer Science, 92 (1992), pp. 301-307.
Jack H. Lutz, An upward measure separation theorem, Theoretical Computer Science 81 (1991), pp. 127-135.
Jack H. Lutz, Pseudorandom sources for BPP, Journal of Computer and System Sciences 41 (1990), pp. 307-320.
Jack H. Lutz, Category and measure in complexity classes, SIAM Journal on Computing 19 (1990), pp. 1100-1131.

Older 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. 24-38.
Jack H. Lutz, Effective fractal dimensions (invited lecture at the International Conference on Computability and Complexity in Analysis, Cincinnati, OH, August 28-30, 2003), Mathematical Logic Quarterly 51 (2005), pp. 62-72.
Jack H. Lutz and Elvira Mayordomo, Twelve problems in resource-bounded measure, in the Computational Complexity Column (E. Allender, ed.), Bulletin of the European Association for Theoretical Computer Science 68 (1999), pp. 64-80, and in G. Paun, G. Rozenberg, and A. Salomaa (eds.), Current Trends in Theoretical Computer Science: Entering the 21st Century, World Scientific, 2001, pp. 83-101.
- 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, Springer-Verlag, 1997, pp. 225-254.

formatted by Markdeep 1.18

✒