Top national research honor goes to Mark Braverman

By The Office of Engineering Communications and the National Science Foundation 

Mark Braverman, who focuses on core problems of theoretical computer science and applies the results to a broad range of disciplines, has been awarded the National Science Foundation’s highest honor for young researchers, the Alan T. Waterman Award.

Braverman, a professor of computer science, has solved several significant mathematical problems during his career and has focused his research at Princeton on applying theoretical insights to economics, electrical engineering, mathematics and computation. In one example, he applied a fundamental electrical engineering concept, Shannon’s information theory, to a class of computer science questions called communications complexity. Although the theory, which deals with signal processing and data compression, typically concerns one-way communication, Braverman used it to examine the amount of information multiple parties need in order to solve a problem — a critical question for computer science, which has applications to understanding the fundamental limits on tasks ranging from chip design to distributed machine learning. He further examined how the cost of computation grew with the problem’s complexity. His research team has since extended the work to developing the theory of information complexity.

“My long-term goal in this line of work is to get information theory — which has been spectacularly successful at answering questions about communications — to bear on the theory of computational complexity,” he said.

Braverman has also worked extensively in mechanism design, which uses engineering techniques to recommend incentives to achieve economic goals. In one case, Braverman’s research team suggested improvements to the algorithm used to match graduating medical students with medical residency openings at U.S. hospitals. In another project, his team suggested a new family of mechanisms for discouraging health insurance plans from turning away expensive-to-treat patients.

“We believe that machine learning and algorithms have an important role to play in aligning incentives in healthcare,” Braverman said. “These tools have as much a role to play in improving healthcare incentive structures as in improving diagnostics and care.”

Braverman said he encourages students and researchers in his lab to expand their efforts across disciplinary boundaries in order to develop insights that can apply to many different fields.

 “Algorithms are in every part of both the human and natural world, and understanding facts surrounding them is a basic quest — just like the quest of understanding facts about energy, matter or the various parts of the universe,” Braverman said.

Braverman received his doctorate in computer science from the University of Toronto and worked as postdoctoral researcher for Microsoft Research New England. After working as an assistant professor with a joint appointment in mathematics and computer science at the University of Toronto, Braverman joined the Princeton faculty in 2011.

During his doctorate, Braverman developed new techniques for reasoning about the basic computational properties of continuous systems. He applied those techniques to obtain new results about the computational properties of dynamical systems – showing that computational intractability may occur even in highly structured, low-dimensional systems which had been expected to be computationally “simple”.

In his career, Braverman has solved two mathematical problems that eluded researchers for decades: obtaining new bounds on the Grothendieck constant and proving the Linial-Nisan conjecture. The work, and other research insights, have earned him several accolades in his field, including the 2016 European Mathematical Society Prize, the 2016 Presburger Award, the 2014 Stephen Smale Prize, and a 2013 Packard fellowship. Braverman also received an NSF CAREER award in 2012.

Jennifer Dionne, an associate professor of materials science at Stanford University, also received the Waterman this year. Each recipient will receive a $1 million research grant, distributed over five years. The Waterman Award will be presented to Braverman and Dionne at a ceremony held in Washington, D.C., on May 14, 2019.