Communications of the ACM
Tackling Intractable Computing Problems
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