JACK H. LUTZ
(lutz@cs.iastate.edu)
Associate Professor of Computer Science.
Major Interests: Computational complexity, including structure of complexity classes, uniform versus nonuniform complexity, probabilistic complexity, and parallel complexity. Algorithmic information, randomness, pseudorandomness and computational depth.
Current Research: Dr. Lutz does most of his research in two areas: structural complexity theory and algorithmic information theory. In structural complexity he is investigating the structure of complexity classes (deterministic, nondeterministic, probabilistic, and parallel) with respect to such issues as size of Boolean circuits, length of programs, difficulty of approximation, and presence of pseudorandom sequences. In algorithmic information, he is investigating fundamental properties of random and pseudorandom sequences, including adequacy for probabilistic computation, separation of relativized complexity classes, and characterization of complexity classes. In both areas, extensive use is made of new extensions of Lebesgue measure and Baire category developed by Dr. Lutz.
Representative Publications:
"Category and Measure in Complexity Classes," SIAM Journal on Computing 19 (1990), pp. 1100-1131.
"Almost Everywhere High Nonuniform Complexity," Journal of Computer and System Sciences, 44 (1992), pp. 220-258.
"On Languages with Very High Space-Bounded Kolmogorov Complexity" (with R. Book), SIAM Journal on Computing 22 (1993), pp. 395-402.
"A Pseudorandom Oracle Characterization of BPP," SIAM Journal on Computing 22 (1993), pp. 1075-1086.
"An Observation on Probability versus Randomness with Applications to Complexity Classes" (with R. Book and K. Wagner), Mathematical Systems Theory 27 (1994), pp. 201-209.
"Computational Depth and Reducibility" (with J. Lathrop and D. Juedes), Theoretical Computer Science, 132 (1994), pp. 37-70.
"Measure, Stochasticity, and the Density of Hard Languages" (with E. Mayordomo), SIAM Journal on Computing 23 (1994), pp. 762-779.
"The Complexity and Distribution of Hard Problems" (with D. Juedes), SIAM Journal on Computing 24 (1995), pp. 279-295.
"The Global Power of Additional Queries to Random Oracles" (with R. Book and D. Martin, Jr.), Information and Computation, to appear.
"Weakly Hard Problems," SIAM Journal on Computing, to appear.