Mark Braverman Wins the IMU Abacus Medal

Mark Braverman was multilingual by the time he was 17. He calls theoretical computer science his home despite not having a hometown. He said that theoretical computer science was whatever he wanted it to be, sitting between a whiteboard bursting with mathematical equations and a wall decorated with family photos.

For more than a decade, Braverman, 38, has been developing a new theory of interactive communication, expanding and enriching Claude Shannon's work. Researchers can use Braverman's growing framework to translate abstract concepts into mathematical terms. Hard problems can be made into more precise statements. The program has led to new insights into how people interact online.

Braverman has received the highest honor a computer scientist can receive, the IMU Abacus medal. Historians pointed out that the researcher for whom the award was named was a Nazi sympathizer, so it was renamed. The winner of the Abacus medal has to be under 40.

According to the citation, Braverman's contributions to information complexity have led to a deeper understanding of different measures of information cost when two parties communicate with each other. His work paved the way for new coding strategies that are less vulnerable to transmission errors.

Braverman said that the award may make it easier to launch new things. He was quick to dismiss the idea that he is a single genius. He said that there are a lot of talented people in the field.

The mathematician Assaf Naor calls Braverman a "fearless" problem-solver. Naor said that he is very curious and broad. Everything appears to be a nail when you hold a big hammer. Mark has a theory of computer science.

A Mathematical Miracle

The son of a mathematician mother and a physicist father was born in 1984 in Perm, Russia. The family moved to Haifa, Israel, in 1992 after the collapse of the Soviet Union.

Braverman said his parents never pushed him to get into math or computer coding. He said that they made him comfortable with math. He won two bronze medals and a gold at the International Mathematical Olympiad in 1998. He obtained a degree in mathematics and computer science at the Technion in 2001. His family moved to Canada after his mother was appointed to a faculty position. He was in graduate school at the University of Toronto. He was 17 at the time.

He said it was difficult to move when you are older. His travels gave him a bigger view of the world. Braverman said, "You don't have a home, but you know that there are multiple cultures." You can talk to people from different cultures about the basics. He said that theoretical computer science is a good place for ideas from different areas to come together. The far-reaching application of his work to other fields is pointed out in the citations for the awards he has racked up.

His graduate work is very good. As you zoom in, you see the same patterns emerge from Julia sets, which are collections of points that produce dazzling and complicated figures.

Simply input a point to find an output value, and then plug that output value back into the function. The process can be run over and over again to show how the point changes over time. Some starting points will give rise to a sequence of numbers, but others will only get bigger. There is a boundary between points that are close to each other and points that are far away. The shapes are named after Julia. The mathematical field of dynamical systems focuses on how systems change over time.

Braverman wasn't in the field of systems like that. Julia sets aren't usually part of the curriculum, but he was a graduate student in computer science. Braverman's advisor Stephen Cook and the University of Toronto mathematician Michael Yampolsky helped him look at Julia sets in computer science. There is a framework that looks for underlying rules that separate hard problems that can be solved in a reasonable amount of time from super-hard problems that can only be approximated. What rules and functions separate the points that stay close to each other from the points that escape to infinite?

It was a miracle.

It was a good way to look at the issue. He was a bit younger than his peers. It was fun to work with a young person. He was more like a peer.

Braverman wondered what makes a Julia set special in terms of computation. The American mathematician John Milnor established a lot of that work. Braverman was guided by Cook and Yampolsky and began to focus on sets that were difficult to compute, such as complicated functions that required many iteration before revealing whether they stayed close or escaped to infinite. Braverman looked at previous models that had rules for when things could be computed and when they couldn't. The researchers wondered if some functions were so complex that it would be hard to compute their Julia sets.

The perspective of computer science was useful here. Theory of computer science asks if there are problems we can't solve and if we can prove it. It was a field driven by numerical simulations.

Yampolsky said that they might be difficult to compute, but all doable. There were no practical obstacles that could have prevented you from seeing the picture.

Braverman and Yampolsky reached out to Milnor, who was excited by the computer science approach. The group poked and prodded this question for years, looking for ways to show that some Julia sets can't be found. In 2005, inspired by findings from a French group, Braverman and Yampolsky discovered a way forward. Julia sets wereprovably impossible for some functions.

It was a mathematical miracle. A bit of a surprise. Initially, the community was resistant to the idea. Sometimes mathematical ideas have time to spare.

The first paper laid out clear rules for computable Julia sets and presented a method to find functions for which the sets can't be computed. One of the most shocking results was that their way of finding Julia sets was the only way to find them. The foundation for Braverman's master's thesis was created by the research. The computational model used to investigate the Julia sets was described in his thesis and later he and Yampolsky wrote a book about it.

When Braverman began the work, it was an area that was out of fashion. There is a region of ideas in computer science. It gets flooded with results if it's too easy. You can't sustain a community if it's too hard.

Mathematical Optimism

Braverman made a connection with a fellow graduate student named Anna, who would become his future wife. She was born in Russia and was a year behind Braverman in the same school. Braverman said that they never spoke to each other more than a single word. Mark and Anna married in Canada after meeting again with more words.

Braverman spent more time on the road after his PhD. He met theoretical computer scientist Anup Rao while he was at the Institute for Advanced Study. He was a researcher at Microsoft Research New England. Braverman spent a year on the faculty of the University of Toronto after returning to Canada.

He worked on a variety of projects in his search for Goldilocks problems. Braverman liked jumping into the middle of difficult problems, according to Naor. People have been trying to get around a boulder for a long time. Someone is going to come up with a plan to get around it. The person will come up with another plan if it doesn't work. Naor believes that that spirit shows a kind of optimism. He said that if you don't have optimism, you won't get around that boulder. "Mark has it."

He joined the faculty of the Ivy League school. A couple bought a house three blocks from the computer science building after Anna joined the university as a psychologist. It has been his home for a long time. They had one child in 2016 and another in 2018.

Braverman began to work in information complexity after moving to New Jersey. Claude Shannon, who in 1948 laid out the mathematical framework for one person to send a message to another through a channel, was the progenitor of information complexity. The world was introduced to the concept of a "bit" as its basic unit. Shannon wrote that the challenge was to communicate data from one point to another with precise accuracy. It is easy if the data contains a stream of random digits and the channel is noiseless.

It turned out that I enjoy building theories more than I used to, so I decided to build a theory.

The task is difficult if the data has complicated statistical relationships, or if the channel is loud. Shannon borrowed the tools of statistical mechanics to adapt the idea of "entropy" as a number related to the amount of information in a message. Braverman's key insight was to separate the capacity of the channel from the capacity of the message. The ability to execute a communication task is dependent on the ability of the communication channel to handle it. The idea suggests that we should ask what the least amount of entropy is you need to send a message through a channel.

Omri Weinstein is a theoretical computer scientist at the Hebrew University of Jerusalem and one of Braverman's first.

Shannon thought about the phone lines. Extending Shannon's work was the focus of Braverman. He wanted to think about how data is shared and manipulated as well as how it is sent. He was able to see how Shannon's ideas could be applied to the field of communication complexity. Billions of times a day on the internet, two parties communicate with each other to complete a transaction. They only pay attention to how much money was paid and who paid it. It would take repeated messages to reach that goal. It would be difficult to adapt the formalism of information theory to the situation. The first set of problems suggested by the challenge were not like the ones Shannon explored.

Braverman said that he originally wanted to solve some problems, but he now enjoys building theories. Building a theory needed to solve problems, find connections, and recruit graduate students to help. I spent a lot of time working on it.

Finding Answers

The biggest contribution was to build a broad framework that articulated the big, general rules that describe the boundaries of interactive communication.

In situations where one person might not know anything, or if they had no overlap, previous researchers studied how two people would send information. Computer scientists solved scenarios in the 70s about what would happen if two people had the same information. Braverman and his team were the first to show that these exchanges are not data transmission tasks.

Two people have a list of animals and a protocol that they can use to send messages back and forth. It will take a lot of effort to figure out what animals they have in common. Each person has some information to begin with, and every message adds to that information. The communication cost is connected to the increase in information in a paper by Braverman and Rao in 2011.

A version of the direct-sum problem is one of the insights that came from that proof. Does solving multiple copies of a problem have the same communication cost as solving it once and then repeating the task? There is a volume discount. The direct sum is used for data transmission. The problem is the equivalent of a question known as the "interactive compression" problem. Researchers have shown that the answer to the question is no.

Braverman was inspired to look for new ways to maximize data compression when it is shared between two or more people because of the connection between information theory and computational complexity. Braverman and his partners described mathematical rules for suckling information between two or more people. He has looked at how the type of conversation drives the communication cost with his students and his co-workers.

Braverman introduced a new perspective that allowed researchers to articulate the questions and then translate them into math. New communication protocols that may show up in future technologies were identified thanks to Braverman's theory.

A theoretical computer scientist who won the Nevanlinna Prize in 1994 said that the theory is very powerful. Shannon's work is an extension of it.

The majority of Braverman's work is done as he continues to guide the theory. A new field called mechanism design uses the mathematical approaches of economics and game theory to focus his interest. The long-standing challenges of building extensions of Lipschitz functions, a problem in classical analysis and geometry, have been made progress with Naor.

Naor said that he brings insights from computer science which is very different from how he was raised. He has a point of view that is different from mine. It is also an idea and a perspective. He has a philosophy that he has developed.

Winning the Abacus medal won't make a difference. Braverman has deepened his mathematical curiosity over the years, bolstering his life's thesis that tackling thornier problems is a matter of finding the right language to investigate them in. It isn't true in other disciplines that you can't just find a vaccine. Years of incremental advances are required for big advances. Big solutions can be found hidden in an undeciphered language.

He said you can feel like you know nothing but be able to solve the problem in five minutes. He wants to teach that to his students. He said that a big award is a responsibility. You become an ambassador. It shows the students that these are not crazy ideas.