so the salesman is allowed to cross back and forth
between the subsquares to a limited
extent. Formally, this technique is dynamic programming, which is very old.
Then I showed that in order to come
within Epsilon of the optimum solution, you only need to allow something
like 10 over Epsilon crossings. So that
was the idea: If you allow the salesman
to go between these smaller squares a
few times, you can still get a near-op-timum solution, and there’s a simple
dynamic programming language that
enables you to compute the tour with
[continUed FroM p. 128]
You’ve also worked on the use of semidefinite programming, an extension
of linear programming that was developed in the 1980s, in approximation
so semidefinite programming can be
used to find approximations for many
Yes, but the question is, How much
do you lose when you relax the problem? For many problems, people can
quickly come up with instances where
you lose too much. For others, like
graph partitioning, it’s hard to find
counterexamples. That was the status
of semidefinite programs; there were
these methods to approximate various problems, and we didn’t know how
well they worked for many problems.
So while Umesh Vazirani, Satish Rao,
and I were looking at graph partitioning, we came up with a powerful way to
upper bound the amount of approximation, which other people went on
to use for all kinds of things. Then in
some follow-up work with my students
I looked at how to solve semidefinite
programs themselves and showed how
to solve them much more efficiently.
You’ve also been involved with work on
the Unique games conjecture (Ugc),
a deceptively simple proposal formu-
lated by your former student subhash
Khot about the difficulty of assigning
colors to the vertices of a network.
Your recent work with Boaz Barak and
david steurer proved the existence of
a subexponential algorithm for the
Ugc. What are the implications of
It doesn’t quite resolve the UGC, but
it certainly puts it in a very new light.
We don’t know of other NP-complete
problems that have subexponential algorithms, so if the Unique Games problem is NP-complete, as is claimed by
the UGC, then it is a fairly atypical problem. Moreover, many experts think the
subexponential algorithm may be improvable further to disprove the UGC.
another thing you have done to help
solve difficult problems was cofound
princeton’s center for computational
I’m very interested in this broader
issue of computational intractability because it has all kinds of implications. A lot of problems in artificial
intelligence, at least the way they are
phrased, are intractable. What does
that imply either for artificial intelligence or for our understanding of the
brain? If certain physics problems are
intractable, what does that say about
physics? Four member institutions
are involved in the center, and we hold
workshops and meetings.
can you talk about some of the re-
search that has come out of your work
with the center?
The above work on UGC is one. An-
other interesting thing I got into was the
implication of intractability for finance.
This was motivated by all the talk about
financial derivatives and their role in the
financial crash of 2008. When I started
looking at derivatives, I was struck by
the fact that all the computational prob-
lems that were connected with them
seemed to be intractable problems. So
some colleagues and I started discuss-
ing it. In economic theory, it turns out,
there are various justifications for deriv-
atives. One is that they help alleviate the
problem of asynchronous information.
this is the so-called lemon problem of
george akerlof, which addresses the
fact that in a market, some people have
more information than others.
And the idea is that because of
this, markets shouldn’t work, because people who think they have
less information will be too scared to
enter into transactions. In practice,
there are many ways to alleviate the
lemon problem. Economic theory
suggests derivatives mitigate it. What
we showed is that because of computational intractability, there’s something wrong with that theoretical justification. Thus far some experts had
said, “OK, there were problems with
how derivatives were used in real life,
but in theory they are fine.” Our work
raises questions about this.
The old work justifying derivatives
looked at a simplified case where
there’s just one seller who is selling one
derivative. This is not atypical in economic theory, where you study issues
in simplified models. In real life, buyers have to sift through a lot of financial
products in the marketplace, and that’s
where you have to watch out for intractability. We show that computational
intractability arises even when a single
seller is selling many derivatives.
i imagine there are a lot of other settings
that intractability could shed light on.
Our center is working on that, too.
One issue that interests me is the
intractability of data analysis problems. We know intuitively that sifting through large amounts of data is
a tough problem, but computational
intractability can help us formalize it.
But I am interested in understanding
whether or not intractability is actually
a barrier. I suspect that in many cases
the intractability can be bypassed by
Leah hoffmann is a technology writer based in Brooklyn,