Multidisciplinary Aspects of Computation Theory

 

Personnel

Dr. Jack Lutz , Professor of Computer Science, Principal Investigator

Dr. Krishna Athreya , Professor of Statistics & Mathematics, Co-Principal Investigator.

Dr. Pavan Aduri , Assistant Professor of Computer Science, Co-Principal Investigator.

Dr. Vasant Honavar , Professor of Computer Science, Co-Principal Investigator

Summary

This project explores multidisciplinary collection of related problems in which the theory of computing plays a fundamental role. The problems involve a variety of topics in computational complexity, algorithmic information theory, stochastic processes, statistical inference, artificial intelligence, fractal geometry, dynamical systems, game theory, and other areas, but they have several crucial commonalities: The problems are ones that involve computability and/or complexity theory in fundamental conceptual respects. The problems are stochastic in the sense that they or their solutions involve some sort of randomness. The problems are dynamic in the sense that they or their solutions involve analytic or topological methods in addition to the discrete and algebraic methods that more typically arise in the theory of computing. The problems are strategic in the sense that they or their solutions involve the design and analysis of algorithmic strategies for betting, prediction, learning, game-playing, or some other task that is carried out in an environment containing adversity.

Funding

This research is funded in part by a National Science Foundation grant CCF 0344187.