New York University professor Subhash Khot has worked at the cutting edge of what cannot be done with computers since 2001 when, in his third year of graduate school at Princeton University, he formulated the groundbreaking Unique Games Conjecture (UGC). This seemingly simple statement—about the difficulty of solving a specific problem—turned out to have profound implications for the field. Khot has since received some of its highest honors, including the National Science Foundation’s Alan T. Waterman Award, the International Mathematical Union’s Rolf Nevanlinna Prize, and, most recently, the MacArthur Fellowship. Here, he recalls how it happened.
Let’s talk about your background. You grew up in India, and I understand you chose to study computer science without having seen a computer.
It sounds quite strange, but that’s how it was. I didn’t have any exposure to computers or computer science, but I had very good exposure to mathematics in the form of specialized math exams and competitions throughout my school curriculum. And then I had to choose an undergraduate major, which in India one more or less has to declare before one starts the program. At that time, and probably this is the case even now, mathematics wasn’t viewed as a good career option. But friends of mine told me that there are aspects of computer science that are really mathematical, and fortunately, that turned out to be the case.
"In computer science, the best way to show that a certain problem is hard is to take another problem that is already known to be hard, and then reduce that problem to the first problem."
After college, you went to Princeton for your Ph.D.
That decision was rather straightforward. I went to the Indian Institute of Technology in Bombay as an undergrad, and it was a very standard routine for most of the students to join Ph.D. programs in the U.S.
Let’s talk about the Unique Games Conjecture and how you came to develop it.
In my early graduate school days, I was exploring different research topics. One of them was the hardness of approximation. There are many computational problems, known as NP-hard problems, that researchers believe are hard to solve. One can then ask whether one can solve them approximately. When an approximation is allowed, some problems do become easy. But others still remain hard, and the question is whether one can classify problems in terms of hardness of approximating them. This is the topic I started investigating, and in a couple of years, I was led naturally to the Unique Games Conjecture.
It is also a topic that your advisor, Sanjeev Arora—who made extremely influential contributions toward proving the PCP Theorem—is well known for.
Yes, my advisor Sanjeev Arora was involved in the pioneering work on this topic in the early 1990s, known as the PCP Theorem. By the time I started my graduate studies, which was in the early 2000s, large progress had been made, but the field was somehow Stuck. I was reading various things about where the field was and why it was stuck, and I was exploring different questions. Another key researcher in the area, Johan Håstad from Sweden, was visiting the Institute for Advanced Studies in Princeton, and the interaction with him helped me a lot.
In fact, you were working on a problem that Håstad proposed when you devised the UGC in 2002.
Yes, it was about the hardness of approximating 2SAT. Johan had, in some sense, already solved the problem halfway through, and I was thinking about what to do about the second half. Somehow, one fine day, I observed that if one is willing to make the Unique Games Conjecture, then it would solve the second half. It also seemed like a proposal that could break the gridlock in the field. It was a fairly natural proposal to make, but somehow it had not been proposed before, and even after I proposed it, nobody—including me—thought it would be so important.
Can you describe what the UGC posits?
It’s really about one specific problem, about a system of linear equations over, say, integers, with two variables in each equation, and one seeks an assignment that satisfies the maximum number of equations. We do not know whether this problem is hard to solve or not. The conjecture simply states that yes, it is hard to solve. More specifically, the conjecture states that even if there is an assignment that satisfies 99% of the equations, one cannot efficiently find an assignment that satisfies even 1% of the equations.
So what are the implications?
In computer science, the best way to show that a certain problem is hard is to take another problem that is already known to be hard, and then reduce that problem to the first problem. So suppose A and B are two problems, and I already know that A is hard. If I show that A reduces to B, then I can conclude that B must also be hard. Of course, for these reductions to work, I need to start with a hard problem A that I can reduce to other problems, and this is what the UGC does; it identifies a very concrete problem A, as described above, and conjectures that A is hard. Then, if you believe that A is hard, you can reduce A to many, many other problems that researchers have been very interested in, and prove that those are hard, too.
"Broadly speaking, I’m very interested in the interaction between computer science and mathematics, especially geometry and analysis as mathematical areas."
So in a single shot, you prove that a wide range of problems that researchers have been interested in are hard.
Yes, that’s correct. When I first described the proposal to Sanjeev and Johan back in 2002, they were kind of lukewarm about it. Even to me, its full significance wasn’t clear. But I still felt it was worth writing up and publishing a paper about it. And then in the next 10 to 15 years, the consequences started emerging, and there was a slow realization about how important this problem is as a starting point.
Other research directions emerged from the UGC, as well.
Yes, to begin with, one can investigate whether the conjectured problem is indeed hard. That amounts to either proving or disproving the conjecture, and both directions have resulted in very fruitful research.
Some of the reduction mechanisms also turned out to be very powerful.
Yes, that’s another research direction. The idea that one can reduce this problem A to some other problem B sounds natural. However, it turns out that these reductions themselves are quite sophisticated, and to construct them, one needs a lot of new mathematical machinery. Once one develops that machinery, it becomes interesting on its own, in the sense that now it doesn’t even matter whether the conjecture itself is true or false.
What are you working on these days?
I have certainly been working on proving the conjecture, and in the last five years or so, with co-authors, I have proposed a possible plan toward proving it, so I’m excited about that. In particular, I’ve been working on the geometry of Grassmann graphs. These are a very specific class of graphs, and we want to understand their structural properties. In a recent paper with coauthors, we proposed how a better understanding of these graphs would make progress on the UGC.
Are there any other things in the field going on that excite you, or directions you might move in the future?
Broadly speaking, I’m very interested in the interaction between computer science and mathematics, especially geometry and analysis as mathematical areas, and there are certainly many things going on at this intersection. We currently have a large, collaborative project supported by the Simons Foundation on algorithms and geometry. Half of the researchers are from computer science, and half from math. So that’s an ongoing project for the last three years that I’m very happy about.
Can you talk about some of the work that’s come out of the project?
I can cite three striking results that show the back-and-forth interaction between computer science and geometry. I have been involved in work on the monotonicity testing problem in computer science and the related isoperimetric theorems on Boolean hypercube. Assaf Naor has been involved in work on the Sparsest Cut problem in computer science and the related questions about the geometry of Heisenberg group. Oded Regev has been involved in lattice-based cryptography and the related mathematical questions about integer lattices. In all these works, connections between CS and math have been discovered, benefiting both the fields, and it is difficult to say which inspired which.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment