How did those gaps in your knowledge affect your experience of graduate school?

One day [my adviser, Gary Miller,] discovered I’d never heard of NP. It was in a discussion. He said, “This problem looks NP-hard.” I said, “Uh-huh.” He said, “You don’t believe me?” And then he began to prove it, and halfway through he sharply turned to me, because I was just sitting there, and he said, “Do you know what NP-hard is?” I said no.

I thought that was my last day working with him, but he continued and told me the definition. He said, “If you don’t know, it doesn’t matter, as long as you are able to think.” He had a tremendous impact on me.

You’re primarily a theoretician, but throughout your career you’ve made forays into industry. How did this practical work connect to your theoretical research?

In my thesis I developed some geometric methods for partitioning graphs. I was able to show that this family of geometric methods gave provably good cuts for finite-element graphs.

On my mentor’s recommendation, I began to give talks at NASA and Boeing Aerospace. At Boeing, I remember the 3D model of one of the wings already had close to a million elements — they couldn’t even load that into one machine. So they wanted to cut this graph into different components, put them onto different machines with similar computational loads, and minimize communication. That’s why mathematically the formula is a graph cut.

In theoretical computer science, often the underlying mathematical principles are unchanged even when the appearance of the problem changes drastically, from optimization to game theory. When you’re doing the research, it doesn’t feel like a drastic change.

Speaking of game theory, I saw that you helped design a board game. How did that happen?

Oh, I love board games! There are beautiful connections with complexity theory. But mostly I’m the student of my students.

I was giving a talk at Boston University about a beautiful discrete theorem called Sperner’s lemma. It’s very simple in one dimension. You have a line segment where one end is red and one end is blue. You divide it into subsegments [with nodes at both ends] and color each new node either red or blue. Then [no matter how you color them] we know there must be a segment that has both colors.

In two dimensions, it’s very fascinating. You have a triangle, and now you have three colors: One corner is red, one is blue and one is green. You divide this triangle into smaller triangles, so the edges are broken into segments. Each outside edge follows the one-dimensional rule: Nodes can only use the colors of the two ends. Inside the triangle, you can do all three colors any way you like. Sperner’s lemma says that any way you divide it, if you do this coloring, there must be a triangle that has all three colors.

Kyle Burke was my student, working on numerical analysis at the time. He came to my office and said there could be a beautiful board game of Sperner’s lemma: Two players iteratively color a board, and whoever induces a three-color triangle will lose the game. The best board games have winners rather than a tie, and here, clearly someone will win. Why? Because Sperner’s lemma!

I called my friend David Eppstein from Irvine to talk about what makes a good board game. He said, “A good game has simple rules and a beautiful board, and it has to be PSPACE-hard.” Because if you can solve it in polynomial time, a computer would beat you all the time.

So we went through those criteria. Kyle said, “Is this game simple?” I said, “Yeah, it’s one sentence!” He said, “Is this game colorful?” I said, “By design!” Then he said, “If I prove it’s PSPACE-hard, can I get a Ph.D.?” I said yes, and he did. There are many different facets of his theorem. It reveals certain things about fixed points, which are a very beautiful concept in mathematics.