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.
