NSF Expeditions, 2008-2012

This pages contains a list of NSF Expeditions projects that were started in 2007 to 2012.

2007

Expedition to Understand, Cope with, and Benefit From Intractability

• Lead PI: Sanjeev Arora (Princeton)
• Collaborators: Rutgers University, New York University and the Institute for Advanced Study
• 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.

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

• Lead PI: Carla Gomes (Cornell)
• Collaborators: Bowdoin College, the Conservation Fund, Howard University, Oregon State University and the Pacific Northwest National Laboratory
• 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.

Open Programmable Mobile Internet 2020

• Lead PI: Nick McKeown (Stanford)
• 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.

Molecular Programming Project

• Lead PI: Eric Winfree (Caltech)
• Collaborators: U. Washington
• 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.

2012

An Expedition in Computing for Compiling Functional Physical Machines

• Lead PI: Daniela Rus, Massachusetts Institute of Technology (MIT)
• Collaborators: University of Pennsylvania and Harvard University
• This project envisions a future where 3-D robotic systems can be produced and designed using 2-D desktop technology fabrication methods. If this feat is achieved, it would be possible for the average person to design, customize and print a specialized robot in a matter of hours. Currently, it takes years and many resources to produce, program and design a functioning robot. This new project would completely automate the process, from sketches on-demand, anywhere, and with the skill of a team of professional engineers, leading to potential transformations in advanced manufacturing.

Making Sense at Scale with Algorithms, Machines and People (AMP)

• Lead PI: Michael Franklin, University of California (UC) Berkeley
• AMP will tackle the challenge known as the Big Data problem, in which current data analytics fall short in making sense of the volume, diversity and complexity of data being generated by computers, sensors and scientific instruments; media such as images and video; and free-form tweets, text messages, blogs and documents. AMP seeks to turn this knowledge into insight, to uncover the keys to solving huge societal problems, from improving productivity and efficiency and creating new economic opportunities, to unlocking discoveries in medicine, science and the humanities. The team will focus on key societal applications, including: cancer genomics and personalized medicine; large-scale sensing for traffic prediction, environmental monitoring, and urban planning; and network security.

ExCAPE: Expeditions in Computer Augmented Program Engineering

• Lead PI: Rajeev Alur, University of Pennsylvania
• Collaborators: Cornell, MIT, University of California Los Angeles, University of Illinois at Urbana-Champaign, University of Maryland, University of Michigan, UC Berkeley, Rice University
• ExCAPE aims to change computer programming from the tedious, error-prone, purely manual task it has always been to one in which a programmer and an "automated program synthesis tool" collaborate to generate software that meets its specifications. Computers have revolutionized daily life, and yet the way computers are programmed has changed little in the last several decades. The ExCAPE team brings together expertise in theoretical foundations (computer-aided verification, control theory, program analysis), design methodology (human-computer interaction, model-based design, programming environments), and applications (concurrent programming, network protocols, robotics, system architecture) to pursue research focused on developing new computational engines for transformation and integration of synthesis artifacts, and effective methods for programmer interaction and feedback.

Making Socially Assistive Robots

• Lead PI: Brian Scassellati, Yale University
• Collaborators: MIT, University of Southern California, Stanford University
• This Expedition will develop the fundamental computational techniques that will enable the design, implementation and evaluation of robots that encourage social, emotional and cognitive growth in children. Critical societal problems require sustained, personalized support that supplements the efforts of educators, parents and clinicians. For example, clinicians and families struggle to provide individualized educational services to children with social and cognitive deficits, whose numbers have quadrupled in the U.S. in the last decade alone. In many schools, educators struggle to provide language instruction for children raised in homes where a language other than English is spoken, the fastest-growing segment of the school-age population. This Expedition aims to support the individual needs of these children with socially assistive robots that help to guide the children toward long-term behavioral goals that are customized to the particular needs of each child and that develop and change as the child does.