Jack Lutz
Professor

Office: 206 Atanasoff Phone: (515) 294-9941 Fax: (515) 294-0258 Email: lutz@cs.iastate.edu Homepage: http://www.cs.iastate.edu/~lutz/

Research Interests

Computational Complexity: structure of complexity classes,
resource-bounded measure and dimension, and complexity in
analysis.

Algorithmic Information and Randomness: computational
randomness, constructive dimension, Kolmogorov complexity,
prediction, finite-state dimension, and algorithmic fractal
geometry.

Nanoscale Self-Assembly: information flow, universal
computation, zeta-dimension, and randomness in
self-assembling fractal structures.

Research Areas

Computational Complexity, Theory of Computation

Education

Ph.D.   California Institute of Technology   1987

Honors and Awards

Award for Excellence in Research  College of Liberal Arts and Sciences, 2007

Presidential Young Investigator  National Science Foundation, 1991

Current Grants

Effective Dimensions in the Theory of Computing. Jack H. Lutz. National Science Foundation (2007-2010). $125,000.

FRG: Collaborative Research: Algorithmic Randomness. Jack H. Lutz. National Science Foundation (2007-2010). $30,000.

Representative Publications

Refereed Journal and Conference Publications

Jack H. Lutz. A Divergence Formula for Randomness and Dimension. Computability in Europe: Mathematical Theory and Computational Practice (Fifth Annual Conference), Heidelberg, Germany (July 19-24, 2009), Springer. pp. 342-351, 2009.

Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo. Curves That Must Be Retraced. Sixth International Conference on Computability and Complexity in Analysis, Ljubljana, Slovenia (August 18--22, 2009), Accepted, 2009.

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers. Computability and Complexity in Self-Assembly. Theory of Computing Systems, Accepted, 2009.

James I. Lathrop, Jack H. Lutz, and Scott M. Summers. Strict Self-Assembly of Discrete Sierpinski Triangles. Theoretical Computer Science. Vol. 410. pp. 384-405, 2009.

Xiaoyang Gu and Jack H. Lutz. Dimension Characterizations of Complexity Classes. Computational Complexity. Vol. 17. pp. 459-474, 2008.

Jack H. Lutz and Elvira Mayordomo. Dimensions of Points in Self-Similar Fractals. SIAM Journal on Computing. Vol. 38. pp. 1080-1112, 2008.

Xiaoyang Gu and Jack H. Lutz. Effective Dimensions and Relative Frequencies. Computability in Europe: Logic and Theory of Algorithms (Fourth Annual Conference), Athens, Greece (June 15-20, 2008), Springer. pp. 231-240, 2008.

Jack H. Lutz and Klaus Weihrauch. Connectivity Properties of Dimension Level Sets. Mathematical Logic Quarterly. Vol. 54. pp. 483-491, 2008.

David Doty, Jack H. Lutz, and Satyadev Nandakumar. Finite-State Dimension and Real Arithmetic. Information and Computation. Vol. 205. pp. 1640-1651, 2007.

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. Vol. 37. No. 3. pp. 671-705, 2007.

John M. Hitchcock, Jack H. Lutz, and Sebastiaan Terwijn. The Arithmetical Complexity of Dimension and Randomness. ACM Transactions on Computational Logic. Vol. 8. No. 2. pp. article no. 13, 2007.

Xiaoyang Gu, Jack H. Lutz, and Philippe Moser. Dimensions of Copeland-Erdos Sequences. Information and Computation. Vol. 205. pp. 1317-1333, 2007.

Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo. Points on Computable Curves. IEEE Symposium on Foundations of Computer Science (October 22-24, 2006), Berkeley, CA, IEEE Computer Society Press. pp. 469-474, 2006.

John M. Hitchcock and Jack H. Lutz. Why Computational Complexity Requires Stricter Martingales. Theory of Computing Systems. Vol. 39. pp. 277-296, 2006.

David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser. Zeta-Dimension. Thirtieth International Symposium on Mathematical Foundations of Computer Science (August 29 - September 2, 2005), Gdansk, Poland, Springer-Verlag. pp. 283-294, 2005.

Lance Fortnow and Jack H. Lutz. Prediction and Dimension. Journal of Computer and System Sciences. Vol. 70. pp. 570-589, 2005.

Stephen A. Fenner, Jack H. Lutz, Elvira Mayordomo, and Patrick Reardon. Weakly Useful Sequences. Information and Computation. Vol. 197. pp. 41-54, 2005.

Jack H. Lutz. Effective Fractal Dimensions. Mathematical Logic Quarterly. Vol. 51. pp. 62-72, 2005.

John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Scaled Dimension and Nonuniform Complexity. Journal of Computer and System Sciences. Vol. 69. pp. 97-122, 2004.

Josef M. Breutzmann, David W. Juedes, and Jack H. Lutz. Baire Category and Nowhere Differentiability for Feasible Real Functions. Mathematical Logic Quarterly. Vol. 50. pp. 460-472, 2004.

Jack J. Dai, James I. Lathrop, Jack H. Lutz, and Elvira Mayordomo. Finite-State Dimension. Theoretical Computer Science. Vol. 310. pp. 1-33, 2004.

Jack H. Lutz. Computability versus Exact Computability of Martingales. Information Processing Letters. Vol. 92. pp. 235-237, 2004.

Jack H. Lutz. Dimension in Complexity Classes. SIAM Journal on Computing. Vol. 32. No. 5. pp. 1236-1259, 2003.

Jack H. Lutz. The Dimensions of Individual Strings and Sequences. Information and Computation. Vol. 187. pp. 49-79, 2003.

Jack H. Lutz and Yong Zhao. The Density of Weakly Complete Problems under Adaptive Reductions. SIAM Journal on Computing. Vol. 30. pp. 1197-1210, 2000.

Josef M. Breutzmann and Jack H. Lutz. Equivalence of Measures of Complexity Classes. SIAM Journal on Computing. Vol. 29. pp. 302-326, 2000.

David W. Juedes and Jack H. Lutz. Modeling Time-Bounded Prefix Kolmogorov Complexity. Theory of Computing Systems. Vol. 33. pp. 111-123, 2000.