Research on Algorithms, Complexity, and Database Theory

CCR-9820897论文摘要：这个项目涉及算法、复杂性及其在数据库理论、经济学和组织理论以及生命科学中的应用的研究。在数据库理论中，它探索了数据库工作负载的索引性，谱方法对信息检索问题的适用性，数据挖掘中的新概念和新技术，以及用于拓扑查询的新语言。在应用方面，它研究了组织作为信息加速器的新模型；与资源共享和信息经济有关的算法问题；推断多基因特征遗传基础的复杂性；以及在癌症进展和蛋白质折叠的建模和分析中出现的某些算法问题。在算法和复杂性的核心理论中，研究了输出多项式的电路最小化算法，以及旅行商问题的近似算法。

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.