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.
©2017 ACM 0001-0782/17/02
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
[CONTINUED FROM P. 104]
“Broadly speaking,
I’m very interested
in the interaction
between computer
science and
mathematics,
especially geometry
and analysis as
mathematical areas.”