Jason Koski/University Photography

David Steurer, assistant professor of computer science.

David Steurer, assistant professor of computer science, 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 – especially noteworthy in that the Cornell computer science department is smaller than Stanford’s and others near the top of the list, they pointed out.

An important goal in computer science is to find algorithms (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 until the end of the universe 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 explained.

An example is optimization – finding the best combination of several variables while meeting various constraints. In airline scheduling, calculate 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, find 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 explained. “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, Steurer said, gives for the first time hope that a unified theory for such problems is possible.

“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 explained. “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,” he added. “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.