Posted by Rob Knies

Association for Computing Machinery logo 

Aleksander Madry and David Steurer are both postdoctoral researchers at Microsoft Research New England focused on theoretical computer science. Each of them is intrigued by the challenges posed by graphs, and each has devised new algorithms to address those challenges.

And, as of May 2, both are recipients of Honorable Mention from the Association for Computing Machinery for its 2011 Doctoral Dissertation Award, presented annually to the author or authors of the best doctoral dissertations in computer science and engineering.

Seth Cooper, a computer scientist at the University of Washington, won the award for his dissertation A Framework for Scientific Discovery through Video Games. Cooper, creative director at the university’s Center for Game Science, is co-creator, lead designer, and lead developer of Foldit, a crowdsourced scientific-discovery game that could help solve difficult scientific problems.

Madry and Steurer were the only persons receiving Honorable Mention awards this year.

“We’re thrilled to have Olek and David recognized in this way,” says Jennifer Chayes, Microsoft distinguished scientist and managing director of the New England lab. “Each of them has done deep and original work on algorithms, and we’ve been very lucky to have them at Microsoft Research New England.”

Madry’s Massachusetts Institute of Technology dissertation, From Graphs to Matrices, and Back: New Techniques for Graph Algorithms, addresses the challenge of coping well with massive computing tasks in a graph context. He has developed a set of novel algorithmic tools that advance the state of the art on several fundamental graph problems.

Steurer’s Princeton University dissertation, On the Complexity of Unique Games and Graph Expansion, uses a new algorithm for expansion of graphs across different scales, shedding light on a hard-to-approximate optimization  problem called Unique Games—and could have applications beyond.
Get Microsoft Silverlight
“My dissertation is about approximation algorithms and their limitations,” he explains. “In recent years, the Unique Games Conjecture has emerged as a central open question in this field. The results of my thesis shed new light on this conjecture. The thesis shows close connection to questions about the expansion of small sets in graphs, and it develops surprising approximation algorithms for the underlying optimization problem.

The Honorable Mention awards include a $10,000 award. While that is certainly appreciated, Steurer and Madry both say they get something less tangible but more powerful—motivation.

“It’s a great honor that my thesis was recognized among all computer-science dissertations in 2011,” says Steurer, who this fall will be joining Cornell University as an assistant professor. “I take the recognition as a sign that the research community appreciates my work. I am very grateful for this support. The recognition also serves as additional motivation for me to continue the line of work in my thesis.”

Madry takes a historical view of the value of the honor.

“Winning this Honorable Mention means that my thesis was judged to be in the top three in the world of all the theses written last year across all the fields of computer science,” says Madry, who will join Switzerland’s École Polytechnique Fédérale de Lausanne in July. “Needless to say, I was very happy.

“Historically, all the people from my field that won either the Dissertation Award or an Honorable Mention went on to have very successful careers,” he adds. “Therefore, earning this accolade is not only a very satisfying recognition of all the work I have done over four years of my Ph.D. studies, but also, it is a sign that the community views me as a promising researcher.

“I find it a bit intimidating—but very motivating.”