Follow us on Instagram
Try our latest crossword

Computer Science professor Mark Braverman awarded Waterman Award for work in algorithms

David Kelly Crow / Office of Communications
David Kelly Crow / Office of Communications

Last week, the National Science Foundation (NSF) named Mark Braverman, a computer science professor at the University, as one of two recipients of this year’s Alan T. Waterman Award for his work on algorithms and computational complexity theory.

In an email to the The Daily Princetonian, Jennifer Rexford, the chair of the computer science department, explained that this honor is “a reflection of Mark Braverman’s deep and sustained contributions to scientific knowledge.”


Braverman received his Ph.D. at the University of Toronto in 2008 and conducted post-doctoral research at Microsoft Research New England in Cambridge, Mass. After a joint appointment in mathematics and computer science as an assistant professor at the University of Toronto, Braverman joined the University’s computer science faculty in 2011.

As a postdoc at Microsoft, Braverman worked on projects involving predictive analytics of medical data. In healthcare, Braverman said, there are restrictions that don’t exist in other markets, including who has access to patient records.

Braverman proposed improvements to the current algorithms used to match medical residents to U.S. hospitals, and used machine learning to study factors that lead to the re-hospitalization of patients.

Even though his research has clear applications in the healthcare industry, it is still mostly theoretical.

Braverman said that “rather than solving a concrete problem,” he has greater interest in “exploring what kind of solutions are even plausible.”

Braverman’s core research contributions are in the area of algorithms and computational complexity, an area of study which aims to understand the limits of what can be accomplished computationally. At the most basic level, his work focuses on the interplay between information theory quantities and computation. In some cases, he identifies mathematical explanations for why progress is so difficult.


“My favorite thing is to prove impossibility results,” he said. 

Braverman hopes that these information-theoretic techniques will lead to the development of more precise tools for reasoning about the performance of real-life systems.

“In computing, we don’t have good theories that work beyond two orders of magnitude, which is something by definition practitioners care about,” Braverman said.

Braverman said that on the hardware front, there is an increased focus on task-specific hardware and other forms of hardware optimization, leading to new theoretical challenges in capturing the performance of those systems.

Get the best of ‘the Prince’ delivered straight to your inbox. Subscribe now »

Most recently, Braverman has been studying mechanism designs, which he defines as “algorithm design where data comes from self-interested participants.”

Braverman said that the number of implementable algorithms has been increasing. He added that there are still countless challenges in mechanism design theory, which is still a relatively underexplored area.

Braverman believes that mechanism design is more akin to a social science than a natural science.

“A lot of the time, it’s not about solving the problem,” he said. “It’s about the meta properties of algorithms and the responses they elicit from participants.”

He currently teaches COS 598B, a graduate seminar on Topics in Algorithmic Mechanism Design.

Outside of the classroom, Braverman is a mentor and role model to undergraduates and postdocs alike. Grace Guan ‘20, one of his students, conducts research involving the applications of mechanism design in healthcare with the goal of better understanding insurers’ incentives and strategic responses to the Affordable Care Act risk adjustment program.

Beyond helping with small things such as course selection, Guan says that Braverman sets aside time every week to discuss their research and her long term career.

“Professor Braverman has been able to come up with research problems that are manageable yet stimulating for an undergraduate like me,” she said. “He comments on my other research projects outside his main expertise, which I really appreciate.”

For Braverman, his relationship with his students are not one-sided.

“I’ve been learning a lot from my students and postdocs,” he remarked. “My interests are usually pretty broad, so a lot of the time, I rely on them to teach me things.”

Rexford described Braverman as a “wonderful departmental citizen” and added that “he is an unusually gifted teacher and also plays several important service roles in the department, always with great attention, insight, and care.”

“He immediately cuts through the considerable practical details to crystalize the essence of the hard underlying technical problem and an elegant and efficient solution,” Rexford said of her colleague. “The department is excited and proud for Mark, and delighted that we have an intellectually rich environment where faculty can do their best scholarship.”

Guan said that Braverman’s award “dually acknowledges the Princeton [computer science] department’s prowess and his own success as a young researcher,” adding that this will hopefully allow “more students to be attracted to the CS program or give greater visibility to the area Professor Braverman researches.”

The Alan T. Waterman Award is the United States’ highest honorary award presented to scientists under the age of 40 who completed their Ph.D.s less than 10 years ago. Awardees receive a grant of $1 million over a five-year period for scientific research and advanced study at an institution of the recipient’s choice.

According to the NSF’s website, recipients of the Waterman award have “demonstrated exceptional individual achievement in scientific or engineering research of sufficient quality, originality, innovation, and significant impact on the field so as to situate him or her as a leader among peers.”

The United States Congress established the Waterman Award in August 1975 in honor of the NSF’s first director and to mark the 25th anniversary of the organization’s founding.

Braverman has been awarded several honors previously before, including the 2016 European Mathematical Society Prize, the 2016 Presburger Award, the 2014 Stephen Smale Prize, the 2013 Packard Fellowship, and an NSF CAREER award in 2012.

Stanford University professor Jennifer Dionne, who studies materials science, was the other recipient this year. Braverman and Dionne will receive their awards at a ceremony in Washington, D.C. on May 14, 2019.