ITR: Algorithms: From Theory to Application

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

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.