The PI and his collaborators have been involved in: (a) some of the subfields of theory that have witnessed impressive recent advances (approximation algorithms, on-line algorithms), (b) a subfield that has been very successful and relevant, but is facing new challenges (database theory), and(c) ``exporting'' complexity-theoretic ideas to other disciplines (e.g., Game Theory, Economics, and Artificial Intelligence). The goals of this project include: (1) The deepening and broadening of recent advances in approximation algorithms and on-line algorithms, by attacking fundamental problems such as the Euclidean traveling salesman problem and the k-server conjecture; (2) The study of alternative models and metrics, for example, in relation to on-line algorithms for storage allocation, that are closer to reality and to computational practice; (3) The introduction of approximation and on-line problems that in a small way contribute to our understanding of the computational requirements of a global information environment; (4) The study of database-theoretic problems that are posed by novel media and heterogeneity; (5) The continuation of PI's research program that considers problems from other disciplines (such as, Game Theory, Genetics, and Artificial Intelligence) from a complexity-theoretic point of view.***
