Princeton University is the lead institution for a new $10 million National Science Foundation grant that will fund research on "intractability" -- a concept that has profound implications for a broad range of fields, from e-commerce to quantum computing.
"Our proposed research will address some of the deepest questions in computer science," said Sanjeev Arora, a professor of computer science at Princeton and the director of the Center for Theoretical Computer Science.
Even with the exponential increase in computing power of recent decades, thousands of mathematical problems are so difficult that they are considered "intractable," or essentially unsolvable -- even if the world's most clever and powerful computers were harnessed together in an attempt to solve them.
Intractability is a fundamental problem that cuts across science and industry. It limits the ability of scientists to understand nature and restricts the ability of engineers to design systems. By studying intractability, computer scientists and mathematicians hope to establish more clearly which kinds of problems can, or cannot, be solved efficiently by computers.
The grant will help fund a Center for Intractability based at Princeton that will serve as an international hub of unprecedented scope for research, training and outreach. The center will sponsor visiting professorships, workshops, summer schools, popular lectures and Web-based teaching material.
Arora said one important area the researchers would address is cryptography, the science of hiding information from anyone but those who are authorized to see it.
"Most people don't realize that e-commerce rests upon cryptosystems, which, in turn, rest upon problems that we assume are intractable and cannot be decrypted," he said. "But is this true? Every time you do an e-commerce transaction, how do you know that that hasn't been exposed to everybody else in the world? Understanding intractability will help better guide computer security efforts."
Another important area of interest for the researchers is quantum computing, a field in its infancy that aims to build computers by harnessing the physical properties of subatomic particles.
Arora said that the team's research could lead to greater fundamental understanding of how nature goes about solving problems that currently, at least from a human point of view, seem too difficult to solve.
"In quantum computing and in other areas, our model of nature seems to suggest that nature is solving intractable problems," said Arora. "We don't know whether this is a problem with our model or whether nature is doing something which we do not understand."
Bernard Chazelle, the Eugene Higgins Professor of Computer Science at Princeton, noted that "there is a big open question as to whether the problems that we believe are intractable actually are. If we discover that all of these problems that we think are hard are not hard, that would be an earth-shattering discovery. It's hard to think of any other scientific breakthrough that would have more impact today."
Arora, the principal investigator on the new grant, is chair of the Committee for the Advancement of Theoretical Computer Science, an arm of SIGACT, an international organization devoted to the discovery and dissemination of research in theoretical computer science. He teaches a popular undergraduate course called "The Computational Universe," was a 2001 winner of the Gödel Prize and is a former Packard fellow.
Arora and other members of the research team have contributed to some of the biggest discoveries in the field of intractability in the past decade. Chazelle described the group as a "dream team" of researchers in intractability.
In addition to Chazelle, Princeton co-investigators are Boaz Barak, assistant professor of computer science; Moses Charikar, associate professor of computer science; and Robert Tarjan, the James S. McDonnell Distinguished University Professor of Computer Science.
The five-year grant also includes researchers from the Institute for Advanced Study, New York University and Rutgers University.
The co-investigators at the Institute for Advanced Study are computer scientist Russell Impagliazzo and Avi Wigderson, professor in the School of Mathematics and a 1983 Ph.D. recipient from Princeton.
The co-investigators at New York University's Courant Institute of Mathematical Sciences are Subhash Khot, an associate professor of computer science who earned his Ph.D from Princeton in 2003, and Assaf Naor, a professor of mathematics.
The co-investigators at Rutgers University are Eric Allender, chair of the Department of Computer Science; Michael Saks, professor of mathematics; and Mario Szegedy, professor of computer science.
The grant for intractability research is one of four new Expeditions in Computing awards announced Aug. 18 by the Directorate for Computer and Information Science and Engineering at the National Science Foundation.
