“All sorts of surprising connections”: Conversations with Research Fellows Marco Molinaro, Joanna Ochremiak, Matt Weinberg and Christoph Berkholz

by Erica Klarreich, Journalist in Residence

Every year, the Simons Institute for the Theory of Computing welcomes about 30 Research Fellows within its walls. The Research Fellowship program, which is open to theoretical computer scientists who have completed their PhD within the six years preceding their visit, represents “our main vehicle for involving the younger generation of scientists,” said Alistair Sinclair, the Institute’s Associate Director.

Most of the Fellows visit for a single semester, in conjunction with one of the Institute’s research programs, although a few exceptional researchers visit for an entire year. The Fellows are the only Institute visitors who are given full salaries, and they also receive mentorship by senior visitors or local faculty members and follow-up after their visit ends. The Fellowship program is “the level at which we do our most active training,” Sinclair said. “Our Fellows are chosen in a highly selective international competition each year, and we devote a lot of care to them during their visits.”

I spoke with four of the current crop of Fellows about their experiences at the Institute, and the career paths that have led them here.

Integer Programs and Secretaries—Marco Molinaro

When Marco Molinaro was gearing up for his semester at the Simons Institute, he thought he knew what to expect: a bunch of researchers meeting together a couple of times a week, perhaps, but for the most part pursuing their own individual research programs.

Once he arrived at the Institute, however, he realized that this vision couldn’t be farther from the truth. “The vast majority of the time is spent on collaborations,” said Molinaro, a 33-year-old professor at the Pontifical Catholic University of Rio de Janeiro who is a Fellow in the Algorithms and Uncertainty program. “It’s much more intense than I expected.”

Molinaro found his way into theoretical computer science as an undergraduate, upon discovering that it struck what felt to him like a perfect balance between mathematical rigor and concreteness. “I think computer science is a great place to be in if you like mathematics all over,” he said. “It allows you to explore a lot of different mathematical fields in a reasonably cohesive way.”

Molinaro’s work focuses largely on integer programming, a general framework for expressing problems that are about maximizing a function whose variables can take on only integer values. Integer programs arise in a host of practical settings, such as scheduling hospital shifts, major league baseball games, or security routes at Los Angeles International Airport. Yet integer programs can be hard to solve—the general problem is NP-hard—since their discreteness means that tools from the continuous world are not available. Molinaro is currently trying to develop theoretical tools for solving integer programs faster.

Molinaro is also broadly interested studying in algorithms that involve uncertainty, which makes his research a perfect fit for the semester-long program at the Simons Institute. He is working, among other things, on variants of the “secretary” problem, in which an algorithm’s inputs arrive one by one in random order (as occurs, for example, when would-be secretaries are being interviewed to fill a job opening).

The Simons Institute offers an environment that no conference or visiting position in a computer science department can match, Molinaro said. “Because there are so many people here, and they know they’re here for a short time, it brings that intensity,” he said. It can feel overwhelming at times, he said, but it offers an invigorating complement to his professorship in Brazil, which is mellower but offers fewer opportunities for collaboration or talks by top researchers.

“For me it’s great to come here and get all my stimuli, so that when I go back to Brazil I can just unpack all this stuff over time,” he said. “It will take me a couple of years to digest all the things I’m seeing here, for sure.”

From Sociology to Infinite Constraint Satisfaction—Joanna Ochremiak

When Joanna Ochremiak was in elementary school, her father, a mathematician, noticed that she was bored in math class. He started giving her more challenging problems to solve, and in the process instilled a lifelong love of mathematics in her. Even so, Ochremiak’s path to a theoretical computer science Ph.D. has been circuitous.

In high school, she relished the problem-solving challenges of Olympiad-style competitions (and today, she serves as a deputy leader for the Olympiad team from her native Poland). But once she got to university, she said, she was disappointed to find an emphasis on “learning about solutions rather than solving problems yourself.”

Ochremiak had always believed in the value of crossing disciplines, so after four years studying mathematics, she decided to shift gears and get a master’s degree in sociology. “That was a great time,” she said. “I could study whatever I wanted, so I added a bit of philosophy, psychology, and social choice theory.”

When she finished, though, she felt driven to return to mathematics. “I had always wanted to see if I would like doing a Ph.D. in math,” said Ochremiak, who will be taking a postdoctoral position at Paris Diderot University (Paris 7) after her semester at the Simons Institute ends. “I thought, ‘If I don’t try, I will never know if it’s for me.’”

Ochremiak, now 30 years old, entered a Ph.D. program at the University of Warsaw, and soon found herself drawn towards the border between mathematical logic and computer science. Her Ph.D., which she defended in February 2016, deals with an infinite version of the “constraint satisfaction” problem, which asks, given a set of constraints, whether it is possible to satisfy them all at the same time.

Constraint satisfaction problems are ubiquitous in many areas of science, and the classical setting of the problem has been studied for decades, with many applications. However, this setting suffers from a limitation: one can only specify finitely many constraints. In her Ph.D., Ochremiak studied extensions of this framework in which there are infinitely many constraints. Solving such problems is still possible, she showed, provided the variables and constraints have enough symmetry.

For Ochremiak, who loved set theory and topology as an undergraduate, this area of research “just felt good—felt like something I wanted to do,” she said. “In the end it turned out that I found something that’s really my thing.”

Ochremiak, who is a Fellow in the Logical Structures in Computation program, has been dazzled by how many top researchers she has met at the Simons Institute. And here, she said, these researchers—freed from the usual demands of teaching and administrative responsibilities—have all the time in the world to discuss their work and carry out collaborations.

“There have been people whose work I was familiar with, but I had never had the opportunity to talk in depth with them,” she said. “And there are also people and topics I didn’t know about before—all sorts of surprising connections.”

Strategies and Incentives—Matt Weinberg

Matt Weinberg knew since childhood that he wanted to do something “math-y” when he grew up, and when he took an undergraduate algorithms class at Cornell University, he knew that he had found his niche. “I love solving problems,” he said, “and what I found special about algorithms is that you can find hard problems that have a very low barrier to understand what the problems are about. My brother’s an actor, and I can explain even to him why P vs. NP is an important problem.”

Weinberg—now a Fellow in the Algorithms and Uncertainty program—focuses on algorithmic game theory, which considers settings in which an algorithm interacts with human beings, who may act strategically. Algorithm designers cannot control these interactions, but they can try to create incentives for particular types of behavior.

Much of Weinberg’s work centers on the question of why simple auction designs are so ubiquitous in daily life, even though virtually no economic model predicts that simple designs are optimal. Weinberg and his collaborators have turned a uniquely computer-science lens on this problem, proving that in a wide range of settings, simple designs are approximately optimal, which makes them good enough to use for practical purposes.

Recently, Weinberg has started looking beyond auctions to other settings in which it is essential to consider incentives—such as the infamous 2012 Summer Olympics badminton competition, in which four teams intentionally threw matches (and were subsequently kicked out of the tournament). Weinberg’s group has created a measure of how “manipulable” a given tournament structure is, and proved that a single-elimination bracket is the least manipulable tournament design.

Weinberg, 28, is a Simons Institute veteran, having previously visited as a Fellow in the Economics and Computation program in Fall 2015. During that program, he said, “anyone I could possibly have imagined was here for the semester.” At the time, Weinberg got swept up into a group of about 15 researchers who all wanted to learn about Bitcoin, another economic mechanism in which the initial failure to consider incentives led to problematic outcomes. Over the past year, these researchers have written two papers on Bitcoin, with more projects ongoing. “We all took ideas home with us to work on later,” Weinberg said.

There’s no other research experience that is quite like being at the Simons Institute, said Weinberg, who will be starting a faculty position at Princeton University after the semester here ends. “There’s no other institution you could go to and find 50 people who could reasonably co-author papers with you, all in the same building.”

Translating Graph Coloring into Logic—Christoph Berkholz

Christoph Berkholz had a plan all worked out for his semester at the Simons Institute: to finish writing a bunch of papers and proposals that had been waiting for his attention. Back home in Berlin, these tasks had to compete with the more clamorous demands of his two children, as well as his teaching responsibilities as a postdoctoral researcher at the Humboldt University of Berlin. At the Simons Institute, Berkholz figured, he would have the luxury of time—he could even work on weekends.

The weekends have indeed panned out, and the papers and proposals are getting written. But weekdays have been considerably more busy and exciting than Berkholz anticipated, and his goals have correspondingly expanded. With talks to attend virtually every day and a constant parade of new visitors, his time at the Institute has been intense, he said. “Usually you’d have to travel to a lot of conferences to get in contact with so many different people.”

Berkholz, 30, has always been attracted to brainteasers about combinatorial questions, and his research interests reflect this taste. A Fellow in the “Logical Structures in Computation” program, Berkholz works on combinatorial properties of relational structures that can be translated into the language of first-order logic: collections of statements along the lines of “For all x, there is some y such that…”

Berkholz has used methods from first order logic, for example, to understand the running time of algorithms that determine whether two graphs are isomorphic. Such algorithms often distinguish between two graphs by “coloring” vertices in ways that keep track of how the vertices are connected: for example, a vertex might be colored purple if it has four neighbors, or blue if it has two orange neighbors and three green neighbors. If, for example, one of the graphs has four red vertices but the other graph has only two, they cannot be isomorphic.

These coloring statements can be expressed in terms of first order counting logic. By studying the nesting depth of the quantifiers in these statements, Berkholz has been able to establish lower bounds on the running times of certain graph isomorphism algorithms.

Lately, Berkholz has turned his attention to database theory, which can also be formalized in terms of logic. He has been studying how to update queries to a database efficiently if the information in the database changes often, and also—inspired by a boot camp talk at the Simons Institute—how to compute suitable query answers if each entry in a database, instead of being guaranteed to be reliable, comes with a probability that indicates the likelihood that its information is correct.

Berkholz’s semester at the Institute has been the longest he’s been away from his family. So the intensity is a good thing, he said—it has allowed him to pack a research experience that would normally take a year or more into a single semester. “I think it works out,” he said.

Related Articles

Related stories

,