CSAIL Graduate Wins Prestigious ACM Dissertation Award

Sergey Yekhanin, a recent CSAIL doctoral student, has won the prestigious Association for Computing Machinery’s (ACM) Doctoral Dissertation award, carrying with it a $20,000 cash prize.

Yekhanin beat out 116 other dissertations for the prestigious honor. The competition is open to universities around the world, who are invited to nominate one or two Ph.D. theses in any area of computer science or computer engineering. Yekhanin will receive his award at ACM’s annual conference on June 21, in San Francisco, CA.

Yekhanin’s dissertation, “Locally Decodable Codes and Private Information Retrieval Schemes,” considers the task of retrieving information from a huge database without revealing the target of the query.

Consider the example of a stockbroker looking for a particular stock price on the Internet. The broker might not want to reveal her interest in that stock, because it could inadvertently influence the price of it.

In a private information retrieval (PIR) scheme, the broker would send multiple queries to multiple stock exchanges. No single query would reveal the name of the stock that the broker is interested in, but the joint responses from the exchanges would allow her to compute the price of the stock she is looking for. Yekhanin’s novel protocol both achieved privacy and dramatically reduced the amount of communication between the broker and the exchange.

Yekhanin’s dissertation chair was EECS Professor Madhu Sudan. His dissertation committee included Professors Silvio Micali and Ronitt Rubinfeld.

While thrilled by the award, Yekhanin admits that he still finds it somewhat shocking. “Computer science and engineering is a very broad field. There are so many areas I am not aware of, and my dissertation was only one area of it,” Yekhanin said.

Sudan cited the stellar quality of the competing dissertations that ACM had to choose from, but was less surprised by Yekhanin’s win. “This year, the field was extremely competitive,” Sudan said. “But Sergey’s work was very strong. I am particularly happy because the work was initiated entirely by the student, and this serves as a wonderful role model for all gradate students.”

The ACM recognition is the latest in a long line of accolades for Yekhanin and his work. His dissertation also won the George M. Sprowls award for Outstanding Ph.D. thesis from MIT’s department of Electrical Engineering and Computer Science (EECS). Part of his thesis was also featured in ACM’s Annual Symposium on Theory of Computing (STOC) in 2007, where it won the Best Paper Award at the conference.