Publications

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.
  
  

Research Papers

• Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo, Curves that must be retraced, manuscript.
  
  
• Xiaoyang Gu and Jack H. Lutz, Effective dimensions and relative frequencies, Logic and Theory of Algorithms: Proceedings of the Fourth Conference on Computability in Europe (Athens, Greece, June 15-20, 2008), pp. 231-240.
  
  
• James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers, Computability and complexity in self-assembly, Logic and Theory of Algorithms: Proceedings of the Fourth Conference on Computability in Europe (Athens, Greece, June 15-20, 2008), pp. 349-358.
  
  
• 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, to appear.
  
  
• James I. Lathrop, Jack H. Lutz, and Scott M. Summers, Strict self-assembly of discrete Sierpinski triangles, Theoretical Computer Science, to appear.
  
  
• 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 (Berkeley, CA, October 22-24, 2006), IEEE Computer Society Press, 2006, pp. 469-474.
  
  
• Xiaoyang Gu and Jack H. Lutz, Dimension characterizations of complexity classes, Computational Complexity, to appear.
  
  
• 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 (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 (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 (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 (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 (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 (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, Theoretical Computer Science, to appear.
  
  
• 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 Δ₂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 (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.