Communications of the ACM

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 co-authors, 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 lat-tice-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.

Leah Hoffmann is a technology writer based in Piermont, NY.

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.

So in a single shot, you prove that a
wide range of problems that research-
ers 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 realiza-tion 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 direc-
tion. 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 mathemat-
ical machinery. Once one develops that
machinery, it becomes interesting on
I was read-
ing 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 visit-
ing 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 de-
vised 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