Complexity Work: Simply Success

By Rob Knies, Managing Editor, Microsoft Research

When Mark Braverman (opens in new tab) joined Microsoft Research New England (opens in new tab) as a postdoctoral researcher in July 2008, both he and the founders of the lab knew the move had the potential to be mutually beneficial.

What they couldn’t foresee, though, is the degree to which that potential would be realized.

In the autumn of 2009, the benefits of the partnership can now be assessed—and from both corners, the judgment appears to be a hearty two thumbs up.

Braverman has gotten a taste of what it’s like to work in a dynamic corporate research environment. Microsoft Research has been able to utilize the talents of an uncommonly brilliant young researcher.

And, in the process, Braverman has found time to rake in a trio of prestigious honors.

Call this a win-win-win.

“Mark is amazing in the breadth of his research—from abstract work in complexity theory to practical work on inefficiencies in healthcare policy,” says Jennifer Chayes (opens in new tab), managing director of Microsoft Research New England. “He interacts with almost everyone in the lab, as well as with academia and product groups.  He really enriches the lab.”

That interaction has proved beneficial.

“It’s been very good,” says Braverman, 25, a native of Perm, Russia, who found his way to Cambridge, Mass., via nearly a decade in Haifa, Israel, before embarking on a collegiate career that culminated with a Ph.D. from the University of Toronto in 2008.

He had worked as an intern under Chayes in 2006, when Chayes was still based in Redmond before establishing the New England lab in July 2008.

“That sounded like an exciting new lab,” Braverman says. “It’s a really great job. You get to do what you want. It’s located right here in Cambridge, adjacent to the MIT campus. There are a lot of visitors and seminars.”

His expectations in joining the lab were mainly exploratory in nature: “do research, make new contacts, see what it’s like in an industrial lab, maybe interact with some product groups.”

He wasn’t disappointed.

“It was pretty much what I expected,” Braverman says, “and I had pretty high expectations. I’ve gotten a fair amount done. Getting started with product groups takes a real time investment, but we have some projects with the Health Solutions Group (opens in new tab).”

As Braverman considered his postdoctoral options, the New England lab’s focus on interdisciplinary research appealed to him.

“In my Ph.D.,” he says, “I worked on trying to mix insights from computation and from mathematics, and to investigate how hard it is, the hardness of predicting dynamical systems, systems that evolve over time. That’s part of the broader question: What do computability and complexity theory tell us about real life and what we can do with computers?

“It’s just something I find interesting. It involves a lot of different ideas from different areas, and it’s a very hard field. It’s dominated by open problems. There are more problems than answers.”

Much of Braverman’s work at Microsoft Research New England has focused on his primary interest. But he has explored a new area, as well, and discovered a unique way to collaborate.

“Some of [my projects] are in my core area of complexity theory: proving theorems,” he explains, “mostly, so far, with collaborators outside of Microsoft. The flexibility that they give us is also extremely helpful and very atypical of a postdoc position.

“Other than that, I started learning mechanism design. It’s an intersection of computer science and economics, which is something quite a few people are interested in at this lab.”

Think Auctions

If you’re not quite certain what mechanism design is, you might know more than you think—particularly if you’ve ever used eBay.

“An auction is a type of mechanism,” Braverman states. “If you have a number of selfish players, and you want to accomplish some common goals, and you want to design a set of procedures, this lets you do that.”

And then there’s his nascent work in health research.

“I believe that you can really improve treatment and outcomes and deficiencies through better applying computational learning to data that is being collected,” Braverman says. “There is a big push to adopt electronic medical records, and that means that a lot of data is pouring into hospital data centers. We are looking at ways to mine this data, to put it to good use.”

The potential effect of such work is monumental.

“It could do many different things,” he says. “In an ideal world, it would mean cheaper treatments with fewer mistakes, more informed decisions that are made based on trial cases.

“We tackle specific problems, but also, the tests are being implemented. It’s the relative practical issues that we need to look at. The data is not always that clean. There are relative mistakes at the entry point. There are a lot of considerations, technical and economic, in implementing it. We are trying to figure out what’s possible. Actually, the quality of data is becoming better, so it’s figuring out what we can do with the current quality of data, while also looking forward to when the data is even better. It’s an ongoing effort.”

In addition to his day job, Braverman also has found himself with the pleasant chore of accepting a recent plethora of awards. For example, during the Institute of Electrical and Electronics Engineers’ Conference on Computational Complexity, held July 15-18 in Paris, his paper Poly-logarithmic independence fools AC0 circuits (opens in new tab) was named the conference’s best.

The paper’s abstract states: “We prove that poly-sized AC⁰ circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one.”

Sounds impressive, but what does that mean?

“It’s a question of what looks random,” Braverman explains. “It’s a very big area in complexity theory: ‘Here is some computing device. What looks random to it?’ Obviously, if you have truly random bits, they look random to it. But can we somehow generate things that look random without actually being random?

“In the programming language C, when you use the random function, it doesn’t really produce random bits. It uses some algorithm to produce things that look random. It’s a big area called derandomization, and it’s related to cryptography. When you encrypt something, you want it to look random to someone who doesn’t have the key. AC⁰ circuits are a specific model of computation, and this shows that a very broad set of distributions that are not uniformly random look random to this model.”

More Honors

Braverman also won a pair of doctoral prizes this year, one from the Canadian Mathematical Society, which stated that his work “is motivated by questions on how computability and complexity theory affect our understanding of real-world phenomena. … He has worked on projects in a wide range of areas of mathematics and computer science, including stochastic derandomization, pseudorandomness, and applications of information theory to communication complexity. Braverman’s work has opened up new avenues of research in dynamical systems and computer science, and will be of lasting significance to both fields.”

In fact, a book related to the work that resulted in this prize, co-written by Braverman and colleague Michael Yampolsky and entitled Computability of Julia Sets (opens in new tab), was published in 2008.

And that’s not all. Braverman also was one of four winners of doctoral prizes from the Natural Sciences and Engineering Research Council of Canada, along with Anne Broadbent of the Université de Montréal, James Day of the University of Alberta, and Gregory Welch of the University of Windsor.

“It’s great, of course,” Braverman says, “and it’s obviously pleasant to be recognized. But doing the work is what counts. The recognition allows you to carry on with the work, and you get more resources in the long run to pursue the work that you want.”

He has learned to take such accolades in stride. Nine years ago, as an Israeli high schooler, Braverman won a gold medal in the 41st International Mathematics Olympiad, an annual world-championship competition for high school students, held that year in Daejeon, South Korea, with representatives from more than 100 countries. The previous two years, he captured a bronze medal in the same event, which features questions such as:

“Can we find N divisible by just 2,000 different primes, so that N divides 2^N+1? [N may be divisible by a prime power.]”

Try tackling that one at age 16!

Braverman will continue his research at Microsoft Research New England through the end of June 2010, then plans to return to Canada to take a faculty position at the University of Toronto. He’s eager to confront any challenges he encounters.

“I hope to keep learning new things,” he says. “I have a plan of problems in complexity and other areas I hope to solve. But mostly, I just want to stay aware of things and, hopefully, keep doing good work at whatever problems come up.”

Opens in a new tab