Over the past decades, the field of algorithms has developed a toolbox of theoretical techniques that let computer systems to do more with less---to solve harder problems more quickly, using less memory, less communication with other computers, and less of a human user's assistance. One measure of algorithms' research success has been the large number of implemented systems whose designs have been impacted by contributions from the algorithms community. There are many more such successes waiting in the wings for individuals or groups who can draw the connection between an existing algorithmic technique and an existing applied problem. Often, the biggest challenge is recognizing the connection between the practitioner's problem statement and the proper algorithmic solution techniques. This research addresses the process of ``technology transfer'' from the algorithmic toolbox to other computer science domains.

The investigator is working closely with practitioners in various areas of computer science to identify computational problems whose efficient solution would advance their research agendas, dig through the theory toolbox to find techniques that, properly adapted, can be used to efficiently solve those problems, and assist in such adaptation. Domains being addressed include natural language processing, detection of influence pathways in biological networks, traffic route planning that accounts for uncertain delays, network coding for efficient use of communication bandwidth, and efficient use of crowdsourced computation. But rather than being driven by a particular problem domain, the investigator is interested in the overall process for applying theoretical work in algorithms to problems in the practical domain, and is always seeking new applied problems that can benefit from this approach.

Successful completion of the proposed work will contribute advancement to many different branches of computer science. The contributions to other branches of computer science will, in turn, allow them to achieve their goals of broad impact on society. The investigator also hopes to increase the general sense of connection between theoreticians and practitioners, yielding increased collaborations and successful applications of algorithms to theory beyond those made directly during this project. The project will contribute to research training by continuing to employ large numbers of students with attention given to gender diversity.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
1117381
Program Officer
Balasubramanian Kalyanasundaram
Project Start
Project End
Budget Start
2011-07-01
Budget End
2014-06-30
Support Year
Fiscal Year
2011
Total Cost
$400,000
Indirect Cost
Name
Massachusetts Institute of Technology
Department
Type
DUNS #
City
Cambridge
State
MA
Country
United States
Zip Code
02139