Communications of the ACM
Microsoft Fellow David Steurer Seeks ltimate Algorithm
Cornell's David Steurer is on a "quest for a unified theory of efficient algorithms for difficult computational problems."
Credit: Jason Koski / Cornell University
David Steurer, assistant professor of computer science at Cornell University, has been awarded a Microsoft Research Faculty Fellowship to support research to find the "laws of efficient computation," which might settle a long-standing controversy in computer science and lead to a new way to solve some very hard problems.
One of seven Microsoft fellowships given worldwide this year to support early career researchers, Steurer's award provides $200,000 for two years, along with access to software, invitations to conferences, and engagements with Microsoft researchers. Cornell is second only to Stanford University in the number of faculty members receiving Microsoft fellowships, according to the Department of Computer Science, which is smaller than Stanford's, the department says.
An important goal in computer science is to find algorithms (software-based methods to attack a problem) that make the most efficient use of computer time. Some problems can be so complicated that even the fastest computers would take an inordinate amount of time to complete the calculation.
"It is not clear if we are just overlooking a cleverer algorithm that could solve those problems or if these problems are inherently intractable, meaning it doesn't matter how fast your computer is, you simply cannot solve it," Steurer says.
An example is optimization — finding the best combination of several variables while meeting various constraints. In airline scheduling, that involves calculating how to serve the most passengers with the fewest delays while using the minimum amount of fuel and ensuring pilots get required rest and sleep between flights. In social science, it's finding a "community" on Facebook whose members have more friends inside the group than outside.
To solve such problems a computer must calculate all possible combinations and compare them. That could be one of those endless calculations, so computer scientists turn to approximations: Settle for an answer that's not perfect but close enough to be useful. There are lots of ways to do this in specific situations, but Steurer is looking for a "theory of everything."
"People try to tailor their algorithm to the problem they want to solve," he says. "In this research we have a candidate algorithm that we don't have to tailor but works as well as the best known algorithm."
The challenge is the Unique Games Conjecture (UGC), which says that you absolutely cannot get an approximation that is more accurate than the one you get by a method described in the UGC. (In mathematics, a conjecture is something that seems likely but hasn't been formally proven — yet.)
Steurer has already solved several difficult problems with the "sum of squares method" — a way of reasoning about all potential solutions without actually looking at them — which he believes can be refined to solve the approximation problem. If it works, that would disprove the UGC, send shockwaves through the computer science community, and lead to a general algorithm that could be applied to any computationally intensive problem. The work going on around the UGC and the sum of squares method gives hope for the first time that a unified theory for such problems is possible, Steurer says.
"The UGC predicts that for a wide range of problems, either a concrete meta-algorithm can solve it or no efficient algorithm at all can solve it," he says. "That prediction is remarkable because there are usually lots of different methods to try to solve a problem. So the UGC theory says that there is no point in trying all of these different methods, because either the UGC method works or none at all.
"At the end, it might not be that important if the concrete theory predicted by the UGC is true or not," Steurer adds. "What's more important is that it got us started on the quest for a unified theory of efficient algorithms for difficult computational problems."
Steurer received his Ph.D. from Princeton University and was a postdoctoral researcher at Microsoft Research for two years before joining the Cornell faculty in 2011. He is the recipient of the 2010 FOCS best paper award, the 2011 ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, and an Alfred P. Sloan Research Fellowship.
No entries found