News Release 08-141

New initiative provides substantial funding to pursue ambitious, fundamental research to define future of computing and information

August 18, 2008

This material is available primarily for archival purposes. Telephone numbers or other contact information may be out of date; please see current contact information at media contacts.

The Directorate for Computer and Information Science and Engineering (CISE) at the National Science Foundation (NSF) has established four new Expeditions in Computing. Each of these $10 million grants will allow teams of researchers and educators to pursue far-reaching research agendas that promise significant advances in the computing frontier and great benefit to society.

"We created the Expeditions program to encourage the research community to send us their brightest and boldest ideas," said Jeannette Wing, NSF's assistant director for CISE. "We received an overwhelming response, and I'm delighted with the results of our first annual competition. The four Expeditions together push both the depth and breadth of our field: pursuing longstanding scientific questions of computing, creating a new field of computational sustainability, experimenting with novel technologies for secure, ubiquitous computing and communications of the future, and exploring what we even think of as computing."

The projects are summarized below.

In their Expedition to Understand, Cope with, and Benefit From Intractability, Sanjeev Arora and his collaborators at Princeton University, Rutgers University, New York University and the Institute for Advanced Study will attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The PIs hope to better understand the boundary between the tractable and the intractable. This has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as quantum computing, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics.

In the Expedition Computational Sustainability: Computational Methods for a Sustainable Environment, Economy, and Society, Carla Gomes and her colleagues at Cornell University, Bowdoin College, the Conservation Fund, Howard University, Oregon State University and the Pacific Northwest National Laboratory will explore the development and application of computational methods to enable a sustainable environment, economy and society. By tackling challenges that have not traditionally been addressed by computational approaches, Gomes and her team hope to create a new field of computational sustainability--much like computational biology has arisen in past decades--that will stimulate new research synergies across the areas of constraint optimization, dynamical systems, and machine learning. The research team is highly interdisciplinary, bringing together computer scientists, applied mathematicians, economists, biologists and environmental scientists.

In the Open Programmable Mobile Internet 2020 project, Nick McKeown and his colleages at Stanford University address fundamental issues emerging in the forthcoming broadband wireless mobile revolution. It aims to create an "open" alternative to mobile ubiquitous computing and communication that can spur innovations, which will have a dramatic impact on the choices users will have in the way their data and information is computed, stored and communicated. Their architecture will enable: identity-based computing that frees us from managing a large number of physical and digital keys and enables the development of an integrated security infrastructure; a fluid computing experience that provides seamless access to data and applications anywhere and on any available network; an open, programmable and secure environment, where it is easy both to write and deploy applications on devices that are secure and to enable remote services and backup storage in the cloud; and fast radio access networks where new radio technology mitigates interference, exploits diversity at all levels and improves transmit channel knowledge.

In the Molecular Programming Project, Erik Winfree and his colleagues at the California Institute of Technology and University of Washington will develop fundamental computer science principles for programming information-bearing molecules like DNA and RNA polymers and demonstrate their application experimentally. Inspired by the biomolecular programs of life--from the low-level operating system controlling cell metabolism to the high-level code for development, the process by which a single cell becomes an entire organism--Winfree and his colleagues are working to create analogous molecular programs using non-living chemistry. The objects of their study, molecular programs, are collections of molecules that may perform a computation, fabricate an object or control a system of molecular sensors and actuators. The project aims to develop tools and theories for molecular programming--such as programming languages and compilers--that will enable systematic design and implementation of technological and biotechnological applications that require information processing and decision-making to be embedded within and carried out by chemical processes.

CISE anticipates hosting an Expeditions competition annually, with three new awards anticipated each year. "Because of their exceptional promise, four projects were funded in this, the first year of the program," said Timothy Pinkston, CISE Expeditions program director at NSF. "We can't wait to see the next cohort of proposals in the second annual competition, which is due to begin shortly."

The deadline for preproposal submission to the second annual Expeditions competition is September 10, 2008.

-NSF-

Additional information on the Expeditions in Computing Awards:

Open Programmable Mobile Internet 2020

We are rapidly moving into a new age of widely-deployed, inexpensive, Internet-enabled mobile computing and communication devices. This has the potential to give rise to a whole new generation of services, applications, and modes of behavior to benefit society based on openness in ubiquitous wireless and mobile computing. But this requires re-thinking the computing and communication infrastructure--from the servers in the computing cloud, to the desktop, to the individual handheld devices, to the network that interconnects them all. This Expedition aims to promote innovation and competition by breaking down barriers and constructing bridges for enabling the creation of a truly programmable and open mobile internet (POMI). Expanding on the ubiquitous computing model in which users have unencumbered access to distributed computational and storage resources, this timely experimental systems Expedition will create a virtual data system to enable users to take ownership of their data; a three-tiered computational infrastructure to ease the entry of new Web services; an open network to promote network innovation and make wireless capacity available across heterogeneous and abundant radio networks within a vicinity; and open-source software to promote existing efforts in opening the cell phone and other such handhelds. An at-scale prototype system of infrastructure, devices and applications will be deployed across the Stanford campus--perhaps the most comprehensive experimental deployment of mobile technology for research ever performed by a university. Outreach includes the development and distribution of POMI kits to students at small and underrepresented universities, K-12 schools, and undergraduates at Stanford to engage in creative and inspired discovery through mobile-based education and exploration.

Project Team Members:

Nick McKeown (Lead PI), Stanford University
Dan Boneh, Stanford University
Ramesh Johari, Stanford University
Monica S. Lam, Stanford University
Arogyaswami J. Paulraj, Stanford University
Andrea Goldsmith (Sr. Personnel), Stanford University
Scott R. Klemmer (Sr. Personnel), Stanford University
Christos Kozyrakis (Sr. Personnel), Stanford University
Philip Levis (Sr. Personnel), Stanford University
David Mazieres (Sr. Personnel), Stanford University
John C. Mitchell (Sr. Personnel), Stanford University
Mendel Rosenblum (Sr. Personnel), Stanford University
Fouad Tobagi (Sr. Personnel), Stanford University
Guru Parulkar (Sr. Personnel), Stanford University
Roy Pea (Sr. Personnel), Stanford University
Paul Kim (Sr. Personnel), Stanford University

The Molecular Programming Project

There is great potential for adapting biopolymer molecules such as RNA and DNA to meaningful computational tasks and purposes. Having the ability to program molecules at many orders of magnitude larger scale than at present using new algorithms and software analogues has the potential to change the way we analyze, understand and manipulate molecular systems. It can lead to practical applications of significant benefit to society across a wide range of national initiatives in materials, nano-biotechnology, tissue engineering, regenerative medicine, and many other emerging areas. This ambitious Expedition addresses the exciting challenge of developing initial foundational steps toward creating large-scale molecular programs. This experimental technology Expedition aims to develop a functional abstraction hierarchy to create molecular programming languages, compilers, tools and models; a theoretical framework for the analysis and design of molecular programs; validation of the above utilizing molecular programs with orders of magnitude higher scale of components than at present; and testing of the developed molecular programming technologies on real-world applications. This high-risk/high-payoff research will increase our understanding of the relationship between computation and the physical world, how information can be stored and processed by molecules, and the possibilities and limits of what can be computed and fabricated. Outreach includes summer undergraduate and minority student research fellowships, K-12 visiting days, boot camps, workshops and many other efforts to create a broader molecular programming research community.

Project Team Members:

Erik Winfree (Lead PI), California Institute of Technology
Jehoshua Bruck, California Institute of Technology
Richard Murray, California Institute of Technology
Niles Pierce, California Institute of Technology
Paul Rothemund, California Institute of Technology
Eric Klavins, University of Washington

Understanding, Coping with and Benefiting from IntractibilityCollaborative Research

Computational intractability imposes a limit on the ability to understand nature and design systems. Intractability is a stumbling block for postmen, travelling salesmen, map colorers and millions of others who would like to complete their tasks as efficiently as possible, yet it is the foundation of 21st century cryptography, which in turn is a pillar of electronic commerce. In order to understand, manage and exploit intractability it is imperative that progress be made on proving intractability in many forms and computational models, and on unraveling the interconnections among different forms and uses of intractability. This Expedition will explore an array of diverse but interrelated topics in computational intractability including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics. A "Center for Intractability," the first of its kind, will be based at Princeton. Addressing some of the deepest and hardest theoretical problems standing in the way of significant advancements in computer science, this Expedition involves a high degree of collegial interactivity through collaborations among geographically local participating institutions. Outreach includes an active "Women in Theory" program as well as programs targeting undergraduate and high-school students.

Project Team Members:

Sanjeev Arora (Lead PI), Princeton University
Boaz Barak, Princeton University
Moses Charikar, Princeton University
Bernard Chazelle, Princeton University
Robert E. Tarjan, Princeton University
Mario Szegedy, Rutgers University
Eric W. Allender, Rutgers University
Michael Saks, Rutgers University
Subhash A. Khot, New York University
Assaf Naor, New York University
Russell Impagliazzo (Sr. Personnel), Institute for Advanced Study
Avi Wigderson (Sr. Personnel), Institute for Advanced Study

Computational Sustainability: Computational Methods for a Sustainable Environment, Economy and Society

Balancing environmental, economic and societal needs for a sustainable future encompasses problems of unprecedented size and complexity. With naturally occuring settings, global scale, dynamic and uncertain behavior, mixture of discrete and continuous effects, and highly interactive components, problems associated with sustaining the earth's resources can greatly benefit from computational methods and thinking. There is a key role to be played by computing and information sciences in increasing the efficiency and effectiveness in the way humanity manages and allocates natural resources. Toward that objective, this Expedition aims to establish and nurture a new field of study--Computational Sustainability--driven by a wide range of hard computational problems and critical challenges in the area of sustainability. This applied theoretical Expedition will pursue interdisciplinary research across three computational sustainability themes: conservation and biodiversity; balancing socio-economic demands and the environment; and renewable energy. With the view that natural problems may have a special structure discoverable by machine learning techniques that allows them to be solved even though they are NP-hard, this research attempts to stimulating new research synergies that cross boundaries and merge ideas from combinatorial optimization, dynamical systems, machine learning and constraint reasoning. An "Institute for Computational Sustainability" will be based at Cornell to serve as the nexus of foundational science advancements and practical applications in sustainability. Part of its mission and outreach is to establish a vibrant and diverse research community in the area of computational sustainability, drawing new students into the field from all backgrounds including students from underrepresented groups via summer research experiences and other such proactive activities.

Project Team Members:

Carla Gomes (Lead PI), Cornell University
Jon M. Conrad, Cornell University
John E. Hopcroft, Cornell University
Bart Selman, Cornell University
David B. Shmoys, Cornell University
Mary Lou Zeeman, Bowdoin College
Thomas G. Dietterich, Oregon State University
Heidi J. Albers, Oregon State University
Claire A. Montgomery, Oregon State University
Weng-Keen Wong, Oregon State University
Ole Amundsen (Sr. Personnel), Conservation Fund
Christopher Barrett (Sr. Personnel), Cornell University
Antonio Bento (Sr. Personnel), Cornell University
Daniel Chavarria-Miranda (Sr. Personnel), Pacific Northwest National Laboratory
Francis DiSalvo (Sr. Personnel), Cornell University
John Guckenheimer (Sr. Personnel), Cornell University
Natalie Mahowald (Sr. Personnel), Cornell University
Ken Rosenberg (Sr. Personnel), Cornell University
Heidi Sofia (Sr. Personnel), Pacific Northwest National Laboratory
Steven Strogatz (Sr. Personnel), Cornell University
Larry Walker (Sr. Personnel), Cornell University
Abdul-Aziz Yakubu (Sr. Personnel), Howard University

---

Media Contacts
Maria C. Zacharias, NSF, (703) 292-8070, email: mzachari@nsf.gov

Program Contacts
Timothy M. Pinkston, NSF, (703) 292-8910, email: tpinksto@nsf.gov

Related Websites
The Expeditions solicitation is available at: http://www.nsf.gov/funding/pgm_summ.jsp?pims_id=503169&org=CISE
More information about the Expedition based at CalTech is available here: http://www.dna.caltech.edu/MPP/Docs/MPP_RSV_2008_public.ppt
More information about the Expedition based at Cornell is available here: http://www.cs.cornell.edu/gomes/computational-sustainability/
More information about the Expedition based at Stanford is available here: http://cleanslate.stanford.edu/pomi2020/
More information about the Expedition based at Princeton, Rutgers, NYU and Institute for Advanced Studies is available here: http://www.cs.rutgers.edu/~allender/draft.html

---

The U.S. National Science Foundation propels the nation forward by advancing fundamental research in all fields of science and engineering. NSF supports research and people by providing facilities, instruments and funding to support their ingenuity and sustain the U.S. as a global leader in research and innovation. With a fiscal year 2023 budget of $9.5 billion, NSF funds reach all 50 states through grants to nearly 2,000 colleges, universities and institutions. Each year, NSF receives more than 40,000 competitive proposals and makes about 11,000 new awards. Those awards include support for cooperative research with industry, Arctic and Antarctic research and operations, and U.S. participation in international scientific efforts.

 Get News Updates by Email 

Connect with us online
NSF website: nsf.gov
NSF News: nsf.gov/news
For News Media: nsf.gov/news/newsroom
Statistics: nsf.gov/statistics/
Awards database: nsf.gov/awardsearch/

Follow us on social
Twitter: twitter.com/NSF
Facebook: facebook.com/US.NSF
Instagram: instagram.com/nsfgov