Research on Algorithms, Complexity, and Database Theory

点击翻译按钮获取中文摘要

CCR-9820897PapadimitriouAbstract:This project concerns research on algorithms, complexity, and their applications to database theory, economics and organization theory, and the life sciences. In database theory it explores the indexability of database workloads, the applicability of spectral methods to information retrieval problems, new concepts and techniques in data mining, and novel languages for topological queries. In applications, it investigates a novel model of organizations as information expediters; algorithmic questions that arise in relation to resource sharing and the information economy; the complexity of inferring the genetic basis of multigenic traits; as well as certain algorithmic problems arising in the modeling and analysis of cancer progress and protein folding. In the core theory of algorithms and complexity, it investigates output-polynomial algorithms circuit minimization, and approximate algorithms for the traveling salesman problem.