ITR: Algorithms: From Theory to Application

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

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.