'Dream team' to tackle profound questions in computer science

Aug 20, 2008

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, professor of computer science at Princeton and the director of the new 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 ecommerce 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 ecommerce 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 which 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 or not this is a problem with our model or whether nature is doing something which we do not understand."

Bernard Chazelle, 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 actually all 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 chairman 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 received his Ph.D. in computer science from Berkeley.

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.

The five-year grant includes researchers from Princeton, the Institute for Advanced Study, Rutgers University and New York University.

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 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 Rutgers University are Eric Allender, chairman of the Department of Computer Science; Michael Saks, professor of mathematics; and Mario Szegedy, professor of computer science.

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 grant for intractability research was one of four new Expeditions in Computing awards announced August 18 by the Directorate for Computer and Information Science and Engineering (CISE) at the National Science Foundation (NSF).

Source: Princeton University

Explore further: What the dog-fish and camel-bird can tell us about how our brains work

Related Stories

The majority rules when baboons vote with their feet

Jun 18, 2015

Olive baboon troops decide where to move democratically, despite their hierarchical social order, according to a new report in Science magazine by Smithsonian researchers and colleagues. At the Mpala Resear ...

Recommended for you

Researchers build first working memcomputer prototype

Jul 06, 2015

(Tech Xplore)—A combined team of researchers from the University of California and Politecnico di Torino in Italy has built, for the first time, a working memory-crunching computer (memcomputer) prototype. ...

EU open source software project receives green light

Jul 01, 2015

An open source software project involving the University of Southampton to extend the capacity of computational mathematics and interactive computing environments has received over seven million euros in EU funding.

Can computers be creative?

Jul 01, 2015

The EU-funded 'What-if Machine' (WHIM) project not only generates fictional storylines but also judges their potential usefulness and appeal. It represents a major advance in the field of computational creativity.

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.