Sign In

Communications of the ACM

ACM TechNews

Tackling Intractable Computing Problems

View as: Print Mobile App Share:
Determining which problems can and cannot be solved efficiently, also known as "intractability," is a great challenge for computer scientists.

A goal of the intractability research is develop machine learning algorithms with provable guarantees about the quality of the solutions or the time it will take to run the algorithm.

Credit: Center for Computational Intractability

Princeton University researchers used a $10-million U.S. National Science Foundation (NSF) Expeditions in Computing award to find the sources of intractability, to circumvent intractability when possible using approximations and other means, and to understand the implications of intractability for other areas.

Intractability means it might not always be possible to find accurate, efficient algorithms for some important problems.

The researchers made several theoretical advances, including a new understanding of the Unique Games Conjecture. They found there is an algorithm for solving Unique Games that is better: faster than exponential-time, but still not as fast as polynomial-time.

"Some of the important leaps, for example in the understanding of efficient approximation, public-key cryptography, arithmetic complexity, and the role of intractability in other sciences, seem to happen mainly due to the collaborative environment of the Intractability Center, supported by the NSF Expedition," says Avi Wigderson, a researcher at Princeton's Institute for Advanced Study.

In addition, the project served as a training ground for theoretical computer scientists. "The team also innovated in attracting new talent to theory via new summer programs for undergraduates and high school students, and a highly successful workshop where established women in theory reached out to undergraduate and entering graduate student women," says NSF's Tracey Kimbrel.

From National Science Foundation
View Full Article


Abstracts Copyright © 2016 Information Inc., Bethesda, Maryland, USA


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account