Why Do Some Computer Algorithms Perform Better than Expected?

From search engines to traffic signals, computer algorithms are a central part of our daily lives. Some algorithms, such as those that sort items into categories or identify the shortest path between two points, work as computer programmers expect. They complete their tasks after taking exactly as much time as theory would predict.

But other algorithms seem to defy prediction. Computer scientists have long expected that certain computational tasks cannot be solved; they are too complex. For example, scheduling a baseball season so that every team plays the same number of games at home and away — and with a reasonable amount of travel time for all teams — is an incredibly complex computational task. And yet, certain algorithms solve such problems with ease. Paradoxically, these algorithms seem to do better in the “real world” than they would on a whiteboard.

Sophie Huiberts, a first-year Junior Fellow with the Simons Society of Fellows, explores such conundrums. A theoretical computer scientist, Huiberts is a postdoctoral fellow at Columbia University with Tim Roughgarden. She completed her doctorate at Centrum Wiskunde & Informatica (CWI) in Amsterdam. She earned both her master’s degree in mathematics and her bachelor’s degree in computer science from Utrecht University.

Huiberts and I recently discussed outstanding problems in theoretical computer science. Our conversation has been edited for clarity.

What drew you to computational science, specifically algorithms?

When I was around 14 years old, I became interested in computer programming, and started learning about all these algorithms online that solved different problems. It was exciting to realize that someone had written each of these algorithms out of nothing — they hadn’t been part of the world before. I decided I wanted to do that too, but at the time I didn’t know where to begin.

Fast-forward to Utrecht University, where I was finishing up my master’s degree in mathematics. As I completed my studies — with all the classes and coursework converging in my mind — I came to realize two things. First, I found that I was more interested in understanding why particular types of algorithms worked the way they did, as opposed to writing new algorithms of my own. And second, I realized that the best way to pursue such questions was within a university environment. This led me to pursue my doctorate at CWI, and now my postdoc at Columbia.

So, would you consider yourself to be a theoretician rather than an algorithm designer?

Yes. We certainly need new algorithms to solve different kinds of problems, and I chat with colleagues who do this kind of work all the time. But I personally am trying to understand the properties of different kinds of algorithms writ large, especially those that outperform our expectations by being fast and accurate even when given large and difficult optimization problems to solve.

How do you do that work?

Interestingly, my work rarely involves writing code. I spend much more time at a whiteboard, proving theorems, than at a computer.

I am trying to understand how software works, and my focus is mixed integer linear optimization software. This software uses the algorithms I am interested in to optimize solutions for complex problems. There are around ten of these software packages in existence, and they all basically work the same way.

This is the kind of software behind how baseball games are organized, for example, or how airlines schedule flights to optimize both efficiency and profits. Problems with tens of thousands of variables are solved every day with this type of software.

The fact that all these packages work the same way, algorithmically, suggests to me that there is an underlying logic to explain their efficiency — even in the face of great complexity. But we don’t fully understand that hidden logic yet, and this is what I am trying to uncover.

Along those lines, what was one key discovery you made during your doctorate?

One longstanding question in mathematics centers on polyhedra. These are shapes of three (or more) dimensions, made up of flat polygon faces and shared corners, or vertices — like a soccer ball. In our field, we’re interested in learning the number of hops needed to travel between the polyhedron’s vertices. If you start at one vertex and travel along the adjoining edge, how many edges would you need to traverse to get to the polyhedron’s furthest vertex? Or to put it another way: What is the length of the longest shortest path? Even though this is essentially a question about geometry, it is also important if we want to understand many kinds of algorithms.

During my doctoral research I examined this question from a new angle. Rather than looking at predetermined structured polyhedra, I studied random polytopes. These are non-uniform geometric objects, and their lack of structure gives them each a unique shape. I was able to figure out good estimates on the length of the longest shortest path on these objects.

Understanding the lengths of paths on polyhedra — both traditional polyhedra and random polytypes — is vital for an important algorithm known as the simplex method, which plays a large part in my research. We published this work on the ArXiv and presented it at a conference on computational geometry. The journal version is under review.

What are you working on now?

One of my current projects here at Columbia branches off from this previous work. I’m now studying how to express complicated polyhedra as projections of simpler polyhedra. This may seem like an idle curiosity. But it is actually a hot topic within theoretical computer science that has big implications.

Describing polyhedra efficiently and compactly can benefit optimization methods, meaning that computers can save on resources when using optimization software, because they are doing more with less.

For these formulations, I am now studying how “stable under numerical error” we can make them. Numbers in computer memory can have a certain number of significant digits, meaning that not every number can be represented accurately. An algorithm is deemed stable if this inaccuracy remains in control; the output numbers should only be a little less accurate than the input numbers.

In an earlier project I found a way to quantify such stability for polyhedra, and I am now working to study this property in greater detail. Some polyhedra have formulations that are both very simple and very stable. What we have found, though, is that for other polyhedra there is a trade-off: Any formulation for it must be either complicated or unstable.

Finally, what are your thoughts about the Simons Junior Fellowship?

Prior to arriving at Columbia, all of my training has been in the Netherlands, so it’s been great to have a built-in community now that I am abroad. And that community is so intellectually rich, too; I love talking with biologists, astronomers and chemists and learning about their own work.

Since coming to New York City, I have also begun exploring new areas of research related to mathematics and computer science. I have developed a particular interest in the history of linear optimization, and the five women who were the first to solve this problem by hand in 1948. The contributions of women within the field of computer optimization are less widely known, I’ve found, and I’m excited to shed more light on that history. Being a Simons Junior Fellow gives me the freedom to explore new and interesting topics in my field, both its history and its contemporary challenges — empowering me to immerse myself more fully in my own work and the work of people who have come before me.