I. MOTIVATION Algorithms are ubiqitous, but now increasingly important because of scale of problems. Dichotomy between people with the problems and people doing the algorithms. Need to bring these groups together Two types of interactions needed Practioners <-> theory across problems II. Solution and justification for the center Solution must involve shared resources A. Educational Resources 1. Case studies 2. Application/field specific tutorials (e.g. one oriented torward biologists) 3. New approaches to teaching algorithms 4. Courses for High-school students (e.g Andrew's leap) B. Data and Tools 1. A center for collecting various databases of use to algorithms people 2. A library of algorithms 3. Index of algorithms C. Unique Workshop infrastructure 1. Problem oriented 2. 2-stages (6 months apart) 3. Mediators 4. Incentive plan -- summer funding for algorithms folks 5. Solicit proposals for topic from industrial partners BODY I. MOTIVATION Algorithms are ubiqitous in the use of computers. With the explosion in size and the complexity of problems that are now being solved, mathematically sophisticated algorithms are becoming increasingly important for a wide range of real-world applications. Unfortunately, for several reasons it often takes 10 to 20 years for an algorithm to make it from theory into applications. The reasons range from algorithms not being very practical in their initial form (perhaps because naive assumptions in the model) to the fact that domain experts often do not know about the algorithms. On the other hand we believe that science, engineering and technology can make much more rapid progress if good algorithms are developed more rapidly. [Examples -- eg. astronomical or biological advances are as much going to be furthered by good algorithms for processing data as they will be by new equipment. Perhaps also an example of how smart algorithms will save all sorts of money -- e.g. avoid building the next hubbel telescope] We believe there are two critical interactions that must occur. First there has to be interaction between theory and practice. [SOME JUSTIFICATION.] Second there has to be interaction between the algorithm component of different application areas. The whole reason that algorithms has developed as a filed in its own is that there is a huge base of knowledge, theory and technology that is common across application domains. There is surely not a field that does not require sorting, for example, and more sophisticated techniques such as approximation algorithms, string matching are used across many domains. [Perhaps give examples of problems of not having the interaction--i.e. reinvention of the wheel.] Although the first might be addressed by research effords that consist of both a theory and practical component within a single domain (a handful of such effords are currently funded by the NSF), and the second can be addressed by a concerted efford to study the theory of algorithms (which is handled very well by the theory of computing community within CS), we believe that to speed the progress it is critical to also support a center whose emphasis is on bridging theory and practice across a wide set of domains. This is the case because there are many ideas in the interaction between theory and practice that are common across domains. Furthermore there are many resources that could be greatly leveraged by having them developed across domains. As an example of such an idea, consider the contention between the theory of algorithms that tries to abstract the problem into as simple a model as possible so they can be generic as possible, and the practice in which problems are often complicated by many real-world issues. This contention appears across all domains, and most ideas that could help in one domain could help in another. For example more advanced parameterized cost models might allow problems to remain generic while making them much more applicable across domains. Such research and development of shared resources is best addressed by the STC center form of funding. This is because of the scale of the problem and the large coordination is required. In this proposal (preProposal) we have some specific and innovative proposals of how to coordinate such an efford. We note that this is very much a two way street. How theory will help practice How practice will help theory II. Organization of the center. The center will have three main thrusts. A component involving education, a component involving the development of shared databases and libraries, and a component involving directed research in conjunction with our partners. A. Education The main goals of the education component are the following, o Make algorithms accessible and enjoyable to a wider audience o More rapidly educate domain experts on new algorithms and algorithmic techniques o Educate the theory community how algorithms are used and the needs of the domains To address these goals we propose to do the following 1. Develop algorithm tutorials which are aimed at certain domain experts. For example we might have a tutorial on approximation algorithms designed for biologists. Such a tutorial would differ from a generic tutorial on approximation algorithms in that it would use as examples from biology, and would therefore be much more accessible to biologists. Some of these tutorials would be developed by the permanent members of the center, but we plan to have many of the tutorials developed by outside people. To do this we have requested funds to support outside people to develop these courses. These funds could be used to fund a sabatical or summer monts for faculty to develop these tutorials. The tutorials will consists of a written document, 2. Develop courses for high-school students and minorities that help motivate the importance of algorithms. 3. *************************** FROM THE LETTER OF INTENT In fact, the trend has been for different areas to develop their own algorithms independently, with the result that similar techniques are 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 goal of the proposed center is 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. The center will address critical needs by connecting relevant algorithms to application areas through a set of partnerships with corporations, government laboratories, and other departments within Carnegie Mellon University. The partnerships will consist of o Joint research in which we study and help solve problems presented by our Partners o Educational activities including - workshops - undergraduate and graduate student interns - programs for high-school students o Development of resources such as - a carefully organized collection of pages on algorithms - libraries of algorithms An emphasis of the center will be to develop new ways to interact with the industrial partners, especially with smaller high-tech companies. Traditionally such small companies have not been heavily involved in joint work with Universities, even though they have many features that make them extremely useful for studying applications of scalable algorithms. They have very large data sets at their disposal, they have interesting and difficult problems that need to be solved, and they have a very smart and motivated work-force. As part of the proposal we will develop methodologies for furthering joint research. Some of the difficulties involve issues of ownership, disclosure, and integration. External partners we have contacted and who have expressed interest include the following (given with our contact) Akamai -- Tom Leighton (Chief Scientist) Celera Genomics -- Eugene Myers (VP of Informatics Research) Google -- Monika Henzinger (Director of Research) Intertrust -- Bob Tarjan (Chief Scientist) Sandia National Labs -- Cinthia Phillips WhizBang -- Tom Mitchell (VP and Chief Scientist) Yahoo -- Udi Manber (Chief Scientist) The center will be managed through the School of Computer Science at Carnegie Mellon University, but will involve several other schools within the University including the School of Engineering, the School of Science (Biology, Mathematics and Physics), and the Business School.