'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: Oculus unveils new prototype VR headset

add to favorites email to friend print save as pdf

Related Stories

Will the real unemployment rate please stand up?

Sep 10, 2014

America's unemployment rate—most recently reported as 6.1 percent—has long been used to gauge the country's economic well-being. But a new working paper released by Princeton University's Woodrow Wilson School of Public ...

Climate change: meteorologists preparing for the worst

Aug 21, 2014

Intense aerial turbulence, ice storms and scorching heatwaves, huge ocean waves—the world's climate experts forecast apocalyptic weather over the coming decades at a conference in Montreal that ended Thursday.

The birth of topological spintronics

Jul 23, 2014

The discovery of a new material combination that could lead to a more efficient approach to computer memory and logic will be described in the journal Nature on July 24, 2014. The research, led by Penn S ...

Recommended for you

Oculus unveils new prototype VR headset

Sep 20, 2014

Oculus has unveiled a new prototype of its virtual reality headset. However, the VR company still isn't ready to release a consumer edition.

Who drives Alibaba's Taobao traffic—buyers or sellers?

Sep 18, 2014

As Chinese e-commerce firm Alibaba prepares for what could be the biggest IPO in history, University of Michigan professor Puneet Manchanda dug into its Taobao website data to help solve a lingering chicken-and-egg question.

Computerized emotion detector

Sep 16, 2014

Face recognition software measures various parameters in a mug shot, such as the distance between the person's eyes, the height from lip to top of their nose and various other metrics and then compares it with photos of people ...

User comments : 0