ITR: Algorithms: From Theory to Application

ITR：算法：从理论到应用

• 批准号: 0085982
• 负责人: Guy Blelloch
• 金额: $ 60万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0085982&HistoricalAwards=false
• 关键词: ITR; Algorithms; Theory; Application

With the explosion in connectivity of computers and in the size of data sets available for analysis, mathematically sophisticated algorithms are becoming increasingly crucial for a wide range of real-world applications. Unfortunately, it often takes many years for an algorithm to make it from theory into applications. In fact, the trend has been for different areas to develop their own algorithms independently, with the result that similar techniques reinvented many times in different contexts, and radically new approaches that require an algorithmic level of abstraction take a long time to make it into applications. The intellectual core of this proposal is to create a coordinated effort in "Algorithms from Theory to Practice" that connects the basic development of fundamental algorithms and data structures to their many disparate uses. This work will address critical needs by connecting relevant algorithms to application areas, by exposing and tackling important issues that are common to multiple applications, and by developing fundamentally new approaches to solving key problems via the connections made. This proposal aims to provide impact at a number of different levels. At the lowest level are specific research projects that target key application domains. These include algorithms for mesh generation with applications to scientific simulations and graphics, algorithms for indexing and searching needed for a number of data analysis tasks, and protocols that connect machine learning with cryptography to produce a fundamentally new way for people to securely authenticate to their computers. At a higher level, this proposal will create a center to which researchers in application areas can come to build connections and integrate algorithmic techniques and principles into their own projects. At the highest level, this proposal will create tools to improve the process of moving algorithms from theory to applications more broadly. As one example, the course "Algorithms in the Real World" run by PI Blelloch has already developed a set of web pages detailing how algorithms are used in various applications and what turn out to be the crucial issues involved. A new, extensible version of this database would provide support for theoreticians, practitioners, and educators. We hope the end result to be both a faster pipeline from algorithm design to application, and improved sharing of algorithm techniques across application areas. In addition, we expect the students supported by this effort to fulfill the highest-level goals of this project becoming the next generation vertically-integrated algorithm researchers. The PIs each have a strong track-record in algorithms, both theoretical and applied. Guy Blelloch is developer of the NESL parallel programming language, as well as fast parallel algorithms for a number of core problems. Arvin Blum is known for his work in machine learning and approximation algorithms, and is developer of the Graphphan planning algorithm, used as the basis of many AI planning systems. Manuel Blum is winner of the ACM Turning Award for his work in the foundation of computational complexity theory and its applications to cryptography and program checking. John lafferty is known for his work in language modeling and information retrieval, and is co-developer (along with PI Sleator)of the Link Grammar natural-language parser. Daniel Sleator is winner of this year's ACM Kanellakis "Theory and Practice" award for the development of the Splay Tree data structure, and more recently been developing algorithms for natural language applications.

随着计算机的连接性和可用于分析的数据集的规模的爆炸式增长，数学上复杂的算法对于广泛的现实世界应用变得越来越重要。 不幸的是，一个算法从理论到应用往往需要很多年的时间。 事实上，趋势是不同的领域独立开发自己的算法，结果是类似的技术在不同的背景下被多次重新发明，而需要算法抽象级别的全新方法需要很长时间才能应用于应用程序。 该提案的智力核心是在“从理论到实践的算法”中创建一个协调的努力，将基础算法和数据结构的基本开发与它们的许多不同用途联系起来。 这项工作将通过将相关算法与应用领域联系起来，揭示和解决多个应用程序共同的重要问题，以及通过建立联系来开发解决关键问题的全新方法来解决关键问题，从而满足关键需求。 这项建议旨在在若干不同层面产生影响。 最低一级是针对关键应用领域的具体研究项目。 这些包括网格生成算法，用于科学模拟和图形的应用，用于索引和搜索的算法，用于许多数据分析任务，以及将机器学习与密码学连接起来的协议，为人们提供一种全新的方式来安全地验证他们的计算机。 在更高的层面上，该提案将创建一个中心，应用领域的研究人员可以在其中建立联系，并将算法技术和原理整合到自己的项目中。 在最高层面上，该提案将创建工具，以更广泛地改善算法从理论到应用的过程。 例如，PI Blelloch开设的“真实的世界中的算法”课程已经开发了一套网页，详细介绍了算法如何用于各种应用程序，以及所涉及的关键问题。 这个数据库的一个新的、可扩展的版本将为理论家、实践者和教育工作者提供支持。 我们希望最终的结果是从算法设计到应用程序的更快的流水线，并改善算法技术在应用领域的共享。 此外，我们希望通过这项努力支持的学生能够实现该项目的最高目标，成为下一代垂直集成算法研究人员。每个PI在算法方面都有很好的记录，无论是理论还是应用。 Guy Blelloch是NESL并行编程语言的开发人员，以及许多核心问题的快速并行算法。 阿尔文·布鲁姆以其在机器学习和近似算法方面的工作而闻名，他是Graphphan规划算法的开发者，该算法被用作许多人工智能规划系统的基础。 Manuel Blum因其在计算复杂性理论基础及其在密码学和程序检查中的应用而赢家ACM Turning Award。John lafford以其在语言建模和信息检索方面的工作而闻名，并且是Link Grammar自然语言解析器的联合开发者（沿着PI Sleator）。 丹尼尔Sleator是今年ACM Kanellakis“理论与实践”奖的赢家，他开发了Splay Tree数据结构，最近还开发了自然语言应用程序的算法。