Steve Kautz

Lecturer, Department of Computer Science

Iowa State University, Ames, IA

515-294-4183

email:

Interests

Algorithmic and resource-bounded randomness, nanoscale self-assembly, concurrency, design patterns.
I rejoined the faculty here in January 2008 after spending 8 years in industry. See my CV for details.

Education

Ph.D., Mathematics, Cornell University 1991
M.S., Computer Science, Cornell University, 1990
B.A., Mathematics, California State University, Sacramento, 1985

Publications

"Resource-bounded randomness and compressibility with respect to nonuniform measures," in J.Rolim (ed.), Randomization and Approximation Techniques in Computer Science, Springer Lecture Notes in Computer Science 1269, pages 197-211, 1997.

"An improved zero-one law for algorithmically random sequences," Theoretical Computer Science, 191:185-192, 1998.

"Independence properties of algorithmically random sequences," Technical Report CC/0301013, Computing Research Repository.

"Relative to a random oracle, NP is not small" (with P. Miltersen), Journal of Computer and System Sciences 53:235-250, 1996. Also in Proceedings of the Ninth Annual IEEE Conference on Structure in Complexity Theory, 1994.

"Some sums of some significance" (with M. Dasef), The College Mathematics Journal 28, 1997.

"Degrees of random sets," doctoral dissertation, Cornell University, 1991. (Much of the content of this work will appear in the forthcoming book Algorithmic Randomness and Complexity by Rod Downey and Denis Hirschfeldt.)