Exploring New Frontiers

Expeditions in computing, the National Science Foundation’s two-year-old program encouraging bold experimentation in computer science research, wasn’t necessarily designed to showcase multidisciplinary projects. However, the seven winners of the $10-million, five-year grants are in the vanguard of research in which profound advances in computer science often involve fundamental advances in other disciplines.

“A question that always arises when you give a big award like this is, Would it have been better to have given it to individuals instead of a big award?” says Edmund M. Clarke, a professor of computer science and electrical engineering at Carnegie Mellon University and a recipient of a 2009 Expeditions grant. The answer, Clarke says, is that natural and social sciences are increasingly intertwined with computer science, and “no one of us is a master of all this material.”

Jeannette M. Wing, assistant director of the Computer and Information Science and Engineering (CISE) directorate at the National Science Foundation, says Expeditions was designed in response to concerns from the computer science community that opportunities for expansive and visionary research has lagged in recent years. She says the program provides sufficient funding for a five-year period so the teams can focus on their research and not on writing grant proposals.

“It was really, really important for the CISE community, I felt,” Wing says. “The expectation was that there would be multiple investigators working together in some kind of collaboration. It did not have to be interdisciplinary—that wasn’t a requirement—but because we expected that a proposal would have multiple principal investigators, we wanted the whole to be greater than the sum of the parts.”

The seven Expeditions projects—four were awarded in 2008 and three in 2009—bear out Wing’s vision, with 27 universities and partner research organizations represented. Some projects tackle challenges within computer science itself, others bridge multiple disciplines, but all address a daunting challenge that, like an adventurous expedition, can stimulate one’s imagination.

Back to Top

2009 AWARDEES

 Combining Model Checking and Abstract Interpretation
    Carnegie Mellon University

The Carnegie Mellon project illustrates the symbiosis between critical issues in computer science and other disciplines. Clarke and his colleagues will take principles in model checking and abstract interpretation and apply them to discovering new approaches for treatments of pancreatic cancer and atrial fibrillation, and also to better assure reliability in large-scale embedded systems such as those controlling aircraft functions.

Model checking considers every possible system design state against a designer’s blueprint, and can warn of possible inconsistencies. Its granularity, however, limits the size of the systems it can analyze. Abstract interpretation, in contrast, develops an approximation of a system and preserves properties that need to be assessed. This makes it possible to analyze very large systems, but with less precision than model checking. In their Expeditions project, the researchers will take advantage of the strengths of both methods by tightly integrating the two into what they call MCAI 2.0.

“These domain challenges are at opposite ends of the spectrum of size,” says Clarke, co-winner of the ACM A.M. Turing Award in 2007. (The 2007 Turing Award lecture, “Model Checking: Algorithmic Verification and Debugging,” begins on p. 74.) “One is at the cellular level and the other is at the size of a 747 or Airbus A380—yet we believe that many of the same problems you need for handling complexity at one level will apply to the other as well.”

 Domain-Specific Computing
    University of California, Los Angeles

Jason Cong, professor of computer science and engineering at UCLA’s Center for Domain-Specific Computing, likens the computing platform his team is devising to a human brain.

“If you look to the evolution of humans in the last 5,000 to 10,000 years, I don’t think the number of neurons in the brain has changed that much, nor has the firing speed of neurons; we’re all wired in a very similar way,” Cong says. “So, I believe a lot of progress is done through specialization.”

Just as training in a specific discipline leads one person to perform a given task much more easily than someone who is not similarly trained, Cong’s team will explore creating a computing platform with what he calls a “very flexible” processor core with customizable elements such as operating frequency, voltage, and cache sizes, as well as a domain-specific programming fabric and a radio frequency-based communications fabric that can be tuned to multiple applications. All of the customizable computing and communications elements will be managed by a stack of intelligent software.

The UCLA-led project will focus on adapting these platforms for medical imaging and hemodynamic simulation. A successful imaging domain-specific platform, for instance, could significantly reduce the time a patient must spend in a CT scan machine. Other computational approaches to making scanning and image processing more powerful, such as massive parallel processing by general-purpose computers, are highly inefficient, and cloud computing poses possible data access and privacy issues, Cong says.

---

The seven projects address a daunting challenge that, like an adventurous expedition, can stimulate one’s imagination.

---

 RoboBees: Body, Brain, and Colony
    Harvard University

The RoboBee researchers will explore complementary elements of creating robotic bees using three vectors modeled on live insects—body, brain, and colony. Topics within the body research includes all aspects of flight apparatus, propulsion, and power systems. The brain experiments involve research on the electronic nervous system equivalent of a bee’s brain, including circuits for sensing and decision making. Colony research entails communication and control algorithms that will enable performance beyond the capabilities of an individual. The research team includes experts in biology, computer science, electrical and mechanical engineering, and materials science.

“We are trying to develop micro-mechanical devices, power electronics, and low-power computing fabrics we need to instrument the brain, and to wrap it all together, this notion of developing algorithms and simulating a whole colony of individual agents,” says co-principal investigator Gu-Yeon Wei, associate professor of electrical engineering at Harvard’s School of Engineering and Applied Sciences.

The researchers will also create an exhibit at the Museum of Science in Boston, which will explore the life of bees and the technologies required to create RoboBees. “Bees elicit a lot of excitement and imagery from young to old,” Wei says. “We felt that a good way of tying it together is to share our research in an easily accessible manner.”

Back to Top

2008 AWARDEES

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

This Expedition applies techniques from computer science and related fields, such as information science, operations research, applied mathematics, and statistics, to help manage the balance between environmental, economic, and societal needs for a sustainable future, says Carla Gomes, associate professor of computer science at Cornell University.

“The focus of computational sustainability is on developing computational and mathematical models, methods, and tools for decision making and policy making concerning the management and allocation of resources for sustainable development,” Gomes says.

Gomes is also the director of Cornell’s Institute for Computational Sustainability, which has launched a variety of interdisciplinary projects, such as wildlife conservation through nature reserve selection and corridor design, exploring the impact of renewable energy sources and climate change, policies for fishery management and fish preservation, and equilibrium models for bio-fuel policies.

The institute has fostered the establishment of a research community around this new field by organizing the First International Conference on Computational Sustainability, held in June 2009. It brought together 220 scientists, policymakers, and students in more than 15 disciplines from around the world. (For more about the Cornell conference, see “Computer Science Meets Environmental Science” on p. 23 of the Sept. 2009 issue of Communications.)

 Programmable Open Mobile Internet (POMI)
    Stanford University

The Stanford Expedition aims to create an open Internet for ubiquitous mobile computing and communication networks, thereby increasing users’ choices in the way their data and information is computed, communicated, and stored.

Nick McKeown, associate professor of computer science and electrical engineering at Stanford, says POMI is tackling what he calls the three main barriers to ubiquitous open networks and access. First, “private data is increasingly held by portals that capture our data and restrict the applications we can run against it; in response we are developing the PRPL (PRivate-PubLic) data system,” says McKeown. Second, “there is abundant wireless capacity around us, but most is closed because of closed contracts; in response, we are developing OpenRoads as an experimental platform to allow network service to be separated from the underlying infrastructure.” Lastly, “the current wireline and wireless network is ossified, and innovation in the infrastructure moves at a glacial pace. In response, we are deploying Open-Flow networks on college campuses to facilitate more rapid innovation.”

---

The Stanford project aims to create an open Internet for mobile computing and communications networks.

---

As mobile standards and infrastructure evolve, POMI is an opportunity to develop an open architecture that will create an environment well suited for innovation, competition, and user experience.

 Molecular Programming Project
    California Institute of Technology

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—serve as the key inspiration for this Caltech Expedition.

“The team aims to create analogous molecular programs using non-living chemistry in which computing and decision making will carried out by chemical processes themselves,” says Erik Winfree, associate professor of computer science, computation and neural systems, and bioengineering at Caltech. The Expeditions work can help create a new subdiscipline of computer science, says Winfree, “that will enable a yet-to-be imagined array of applications from chemical circuitry for interacting with biological molecules to molecular robotics and nano-scale computing.”

The Expedition’s first year has witnessed significant advances in all these areas, says Winfree. “As an example, we have developed a compiler for translating abstract formal chemical reaction equations into systems of DNA molecules that react with equivalent dynamics, and we have begun experimental investigations of small circuits generated this way,” he notes.

 Understanding, Coping With, and Benefiting From Intractability
    Princeton University

Sanjeev Arora, professor of computer science at Princeton, says the Center for Computational Intractability, which was created out of this Expeditions grant, “seeks to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms, which has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines, and cast new light on fields such as quantum computing, secure cryptography, and pseudorandomness.”

A key area of interest for the Princeton researchers is the amorphous boundary between problems considered tractable and those considered intractable; an example of this is reliance on cryptographic programs considered intractable, but which may be tractable and are possibly vulnerable to attacks.

In its first year, the Princeton team has carried out monthly day-long meetings focusing on finding new approaches to open problems of intractability, and via workshops, “which have been wildly popular,” and visiting positions, has sought to actively engage other researchers, says Arora. It has also performed outreach activities such as popular talks and a one-month mini-course on computational complexity for high school students in the New Jersey Governor’s School program.

Back to Top

Back to Top

Back to Top

Back to top