The Scientist Who Developed a New Way to Understand Communication
Mark Braverman, a computer scientist at Princeton University specializing in information complexity, has won the 2022 IMU Abacus Medal.
Sasha Maslov for Quanta Magazine
Introduction
By the time he was 17, Mark Braverman had lived in three countries and spoke as many languages. But though he doesn’t have a hometown, he’s quick to call theoretical computer science his home. “Theoretical computer science is whatever you want it to be,” he said in his airy office at Princeton University, 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 transformative new theory of interactive communication, expanding and enriching the pioneering work that Claude Shannon began eight decades ago. Braverman’s growing framework allows researchers to translate abstract concepts like “information” and “knowledge” into precise mathematical terms. As a result, they can recast hard problems as more precise statements. This program has led to new insights into the limitations of computation and speaks directly to the way people interact online.
For this achievement and others, the International Mathematical Union has awarded Braverman the IMU Abacus Medal, widely considered the highest honor a computer scientist can receive. (The award was previously known as the Nevanlinna Prize, but it was renamed after historians pointed out that the Finnish researcher for whom it was named was a Nazi sympathizer.) The Abacus Medal is awarded only once every four years, and the winner must be under 40.
The IMU’s award citation noted that 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 has paved the way for new coding strategies that are less vulnerable to transmission errors and novel approaches to compressing data during transmission and manipulations.
“It’s obviously great to have this kind of recognition, and it might make it easier to launch new things,” said Braverman, who learned of the award in January. But he was also quick to dismiss the idea that he’s some solitary genius. “There are a lot of very talented people,” he said, adding that the field is small but dense with gifted thinkers and productive collaborations.
Braverman’s Princeton colleague, the mathematician Assaf Naor, calls Braverman a “fearless” problem solver. “He is very curious and broad and adventurous,” Naor said. “When you’re holding a big hammer, everything looks like a nail. Mark developed and knows a theory of computer science — and it’s a pretty big hammer.”
A Mathematical Miracle
The son of a mathematician mother and a physicist father, Braverman was born in 1984 in Perm, Russia, an industrial city near the western slopes of the Ural Mountains. Following the collapse of the Soviet Union and its resulting instability, the young family moved to Haifa, Israel, in 1992, when he was 8 years old.
While he’s always been drawn to mathematics and computer coding, Braverman said his parents never pushed. “They got me to a point of being comfortable with math,” he said. He also displayed an early aptitude for the subjects, winning two bronze medals and one gold at the International Mathematical Olympiad in 1998, 1999 and 2000. At the Technion in Haifa, he earned dual degrees in mathematics and computer science in the spring of 2001. Later that year his family moved to Canada, where his mother had secured a faculty appointment in Calgary. That winter, he started graduate school in computer science at the University of Toronto. He was still only 17 years old.
Braverman’s preferred place to think is the sofa in his office. Many of the questions he ponders involve quantifying the hardness of difficult problems.
Sasha Maslov for Quanta Magazine
“It’s hard moving when you are whatever age,” he said. However, his travels afforded a larger worldview. “You don’t have a home, but you understand that there are multiple cultures,” Braverman said. “And you can tell people from one culture about the basic concepts from another.” He’s not just talking about geography: Theoretical computer science is a particularly good place, he said, for ideas from disparate intellectual areas to find a common language. The citations for the awards he has racked up — including a Presburger Award from the European Association for Theoretical Computer Science and a Waterman Award from the National Science Foundation — often point out the far-reaching application of his work to other fields.
His graduate work is a perfect example. Early in his time in Toronto, Braverman became curious about Julia sets, which are collections of points that produce dazzling and complicated fractal figures, meaning that as you zoom in, you see the same patterns emerge.
To find the Julia set of a given polynomial function, simply input a point to find an output value, and then plug that output value back into the function. Running this process over and over — using outputs as inputs — can reveal how the point evolves over iterations. Some starting points will give rise to repeated sequences of numbers, but others will only get larger; these escape to infinity. The boundary between points that orbit reasonably close to where they started and the ones that escape to infinity produces twisting, complicated shapes. These shapes are the Julia set of the function. They feature heavily in the mathematical field of dynamical systems, which focuses on how systems evolve over time.
Only, Braverman wasn’t in the field of dynamical systems. He was a teenage graduate student in the computer science program; Julia sets aren’t usually part of the curriculum. However, his advisor Stephen Cook and the University of Toronto mathematician Michael Yampolsky guided Braverman to previous work looking at Julia sets through the eyes of computer science. That research described fractals in terms of complexity, a framework that (among other things) 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. In Julia sets, Braverman encountered a similar delineation: What rules and functions separate the points that stay close from those that escape to infinity?
It was a mature way to look at the problem. “He was academically young, but also quite a bit younger than his peers,” said Yampolsky. “It was fun to work with someone so young, and so brilliant. He had this intellectual maturity and was more like a peer.”
Braverman started his investigation of the fractals by thinking about the underlying mechanisms: What makes a Julia set special, in terms of computation? Much of that work had been established by the American mathematician John Milnor, now at Stony Brook University. Braverman, guided by Cook and working with Yampolsky, studied Milnor’s strategies and began to focus on sets that were exceptionally difficult to compute, such as complicated functions that required many iterations before revealing whether they stayed close or escaped to infinity. With Cook, Braverman investigated previous models that offered rules for when things could be computed and when they couldn’t. Over time, the researchers began to wonder: Could some functions be so complicated that it would be impossible to compute their Julia sets at all?
This is where the perspective of computer science proved to be invaluable. That kind of question — are there problems we can’t solve, and can we prove it? — is typical of theoretical computer science. In dynamical systems, a field driven by numerical simulations, it bordered on heresy.
“The intuition was that they might be hard to compute, but all doable,” said Yampolsky. “Maybe you just have to wait an obscenely long time to see the picture, but there were no practical obstacles.”
By the time he was 17, Braverman had lived in three countries and spoke three languages. “You don’t have a home, but you understand that there are multiple cultures.”
Sasha Maslov for Quanta Magazine
Braverman and Yampolsky reached out to Milnor, who was excited by this computer science approach to dynamical systems and offered feedback. For years, the group poked and prodded this odd question, looking for ways to show that some Julia sets just can’t be found — an inherently difficult thing to prove. But in 2005, inspired by findings from a French group, Braverman and Yampolsky found a way forward, shattering researchers’ intuitions. They discovered that for some functions, Julia sets weren’t just difficult to compute, they were provably impossible.
“It was one of those mathematical miracles,” Yampolsky said. “And a bit of a shock.” The dynamical systems community was initially resistant to the idea. “But sometimes mathematical ideas have their time, you know?”
Their first paper laid out clear rules for computable Julia sets and presented an algorithm for finding the functions for which the sets can’t be computed. The finding led to a flood of results; one of the most shocking, Yampolsky said, was a proof that their way of finding non-computable Julia sets was in fact the only way to do it. The research formed the foundation first for Braverman’s master’s thesis, and then for his doctoral work at Toronto. His thesis, with Cook, described the computational model used to investigate the Julia sets, and ultimately he and Yampolsky authored a book on the subject, published in 2009
Braverman said that when he started the work, “it was an area that was kind of out of fashion,” but that didn’t bother him. “In computer science there is this Goldilocks region of ideas,” he said. “If it’s too easy, it becomes flooded with results. If it’s too hard, it becomes so sparse that people lose interest and you can’t sustain a community.”
Mathematical Optimism
During graduate school, Braverman made another important connection — this time with a fellow graduate student named Anna, a future psychologist and his future wife. She was also born in Russia and, coincidentally, had been one year behind Braverman in the same elementary school in Haifa. “We never actually spoke to each other more than one word,” Braverman said. But both families eventually moved to Canada, where Mark and Anna met again — this time with more words — and married in 2007.
After his doctorate, Braverman spent more time traveling and making connections. He first spent a month at the Institute for Advanced Study, in Princeton, where he met theoretical computer scientist Anup Rao, with whom he would work steadily for years. After that, he spent two years as a postdoctoral researcher at Microsoft Research New England in Cambridge, Massachusetts. After Microsoft, Braverman returned to Canada, spending a year on the faculty of the University of Toronto.
In his search for Goldilocks problems, he worked on various projects, ranging from health care data mining to unsolved math problems about randomness. Naor, the Princeton mathematician, said Braverman liked jumping right into the middle of tough problems. “Let’s say there’s a boulder in front of you, and people have been trying to get around this boulder for a very long time,” Naor said. Then someone comes along and works out a plan to get around it. If it doesn’t work, the person will find another plan, and then another. That spirit, Naor argues, shows a kind of deep-seated optimism. “If you don’t have optimism, you’re never going to get [around] that boulder,” he said. “And Mark has it.”
Braverman has been in Princeton since 2011, longer than he’s lived anywhere else.
Sasha Maslov for Quanta Magazine
He joined the faculty of Princeton in 2011. Anna joined the university as a clinical psychologist, and the couple bought a house three blocks from the computer science building. At this point, it’s been his home longer than anywhere else. They would go on to have two children – one in 2016, the other in 2018.
Once settled in New Jersey, Braverman began to work in information complexity, the field that Rao had introduced him to in 2008. Information complexity spun out of the larger discipline of information theory, which began with the trailblazing work of Claude Shannon, who in 1948 laid out the mathematical framework for one person to send a message to another through a channel. That paper sought to quantify information, and introduced the world to the concept of a “bit” as its basic, conserved unit. The fundamental challenge, Shannon wrote, was to communicate data from one point to another with exact or near-exact precision. That’s easy enough if the data contain something “simple,” like a stream of random digits, and the channel is noiseless.
But the task quickly becomes tricky if those data have complicated statistical relationships (like the hundreds of thousands of words in the English language) or if the channel is noisy. Borrowing the tools of statistical mechanics, Shannon formalized the idea of data compression and adapted the idea of “entropy” as a quantity related to the amount of information in a message. His key insight, Braverman said, was to separate the entropy of the message itself from the capacity of the channel — the rate at which information is sent. In those terms, a communication task can be executed as long as the entropy of the message does not exceed the capacity of the communication channel. That idea naturally suggests another question: What’s the least amount of entropy you need to send a message through a channel?
“Shannon showed that if the conversation is one-way, where only one party speaks, then you can compress the data optimally,” meaning with the least possible amount of entropy, said Omri Weinstein, a theoretical computer scientist at the Hebrew University of Jerusalem and one of Braverman’s first doctoral students at Princeton.
Shannon was thinking about noisy telephone lines. Braverman focused on extending Shannon’s work beyond one-way transmission. In particular, he wanted to think not only about how data is sent, but about how it’s shared and manipulated, as by an algorithm. He could see ways that Shannon’s ideas could be applied to the field of communication complexity, which asks: What is the communication cost of computation? This question more closely reflects what happens billions of times every day on the internet: Two parties, say a buyer and seller, communicate with each other to accomplish some transaction. They only care about the result — knowing how much money was paid, and to whom — not how they get there. Reaching that goal could require repeated back-and-forth messages. Braverman saw that the formalism of information theory could be adapted to the scenario, but it would be complicated. What math underlies this communication? At first this challenge suggested a set of discrete, approachable problems, not unlike the one-way situations that Shannon originally explored.
“Originally my motivation was to solve some problems, but I enjoy building theories more, so it turned out that there was a theory to be built,” Braverman said. Building a theory meant solving problems, devising proofs, finding connections to other areas, and recruiting graduate students to help. “I spent a good part of the next 10 years working on it.”
Finding Answers
Braverman’s biggest contribution was to build a broad framework that articulated the big, general rules that describe the boundaries of interactive communication — rules that suggest new strategies for compressing and securing data when it’s sent online by algorithms.
Previous researchers had studied how two people might send information back and forth, especially in straightforward situations where one person might not know anything, or if they had no overlapping information. In the 1970s, computer scientists studied and solved scenarios about what happens if the two people had some overlapping information to begin with. But Braverman and his collaborators were the first to show that these exchanges are computational tasks, rather than data transmission tasks.
For example: Imagine two people each have a list of animals and a protocol, which is a way to send messages back and forth. They want to determine what animals they have in common, if any, and how much effort it will take to figure that out. In this situation, each person has some information to start with (they know they’re talking about animals), and every message adds to that information. That increase in information is connected to the communication cost in bits, and a paper by Braverman and Rao in 2011 made that connection tighter than ever before.
Through his work, Braverman has brought mathematical rigor to the way we understand communication between multiple parties, such as in online commerce.
Sasha Maslov for Quanta Magazine
That proof led them to other insights about communication, including a version of a question called the direct-sum problem. It deals with the issue of cost: Does solving multiple copies of a problem have the same communication cost as solving it once and multiplying by the number of repetitions? Or is there a “volume discount”? In the case of data transmission, the direct sum holds. But Braverman and Rao showed that for interactive situations, the problem is the equivalent of a seemingly unrelated question known as the “interactive compression” problem. This asks if two people exchange a million text messages but only learn 1,000 bits of information, could the exchange be compressed to a 1,000-bit conservation instead? Using Braverman and Rao’s work, researchers have shown that the answer is a resounding no.
This connection between information theory and computational complexity also motivated Braverman to look for new ways to optimize data compression when it’s shared between two or more people — something at the heart of online communication. Between 2011 and 2020, Braverman and his collaborators described mathematical rules for compressing information shared between two or more parties. That work begat other questions; with his collaborators and students, for example, he has also investigated how the type of conversation drives the communication cost.
Braverman didn’t just crack open these questions; he introduced a new perspective that allowed researchers first to articulate them and then to translate them into the formal language of math. Braverman’s theory laid the groundwork for exploring these questions and identifying new communication protocols that may show up in future technologies.
“It’s a very powerful theory,” said Avi Wigderson, a theoretical computer scientist at the Institute for Advanced Study who won the Nevanlinna Prize in 1994. “It’s a beautiful and rich and complex extension of Shannon’s work.”
While Braverman continues to guide the theory as his former students and postdocs push it forward, the bulk of his work is done. Now his interests are more focused on a new field called mechanism design, which uses the mathematical approaches of economics and game theory. He’s also recently made progress with Naor on the long-standing challenges of building something called extensions of Lipschitz functions, a problem in classical analysis and geometry.
“He definitely brings insights from computer science which are very different from the way I was brought up,” said Naor. “He has a point of view that differs from the way I think. But it’s also an intuition and a perspective. He has a philosophy that he has developed, a perspective that he brings.”
Winning the Abacus Medal won’t change any of that. If anything, Braverman’s broad mathematical curiosity has deepened over the years, bolstering his life’s thesis: Tackling thorny problems is really a matter of finding the right language to investigate them in. That’s not true in other disciplines: You can’t just stumble across Alpha Centauri, or accidentally discover a Covid-19 vaccine. Big advances typically require technology and years of incremental advances. But in math and computer science, big solutions can be nearby, hidden in an undeciphered language.
“You can basically feel like you know nothing but be within five minutes of solving the problem,” he said. And that’s something he wants to impart to his students and mathematical heirs. A big award like the Abacus, he said, “is a responsibility. It makes you an ambassador. And it makes the case to the students that these are not completely crazy ideas.”
