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 gi