last byte
DOI: 10.1145/2380656.2380681
Leah Hoffmann
Q&a
as Good as it Gets
Sanjeev Arora talks about proof, intractability,
and finding the best way to approximate problems.
sanJeeV arora has long been drawn to
his field’s most intractable challenges.
Born in Rajasthan, India, the Princeton
University professor is best known for
his work on the development of prob-abilistically checkable proofs and a
proof of the PCP theorem, which has
helped distinguish between problems
that can and cannot be approximated
efficiently. He has also contributed new
approximation algorithms for classic
problems like the Euclidean traveling
salesman problem and graph partitioning. More recently, he has cast new
light on the Unique Games Conjecture,
a problem that goes beyond the PCP
theorem to imply that the known approximation algorithms for many simple problems are the best possible.
ing an approximate solution is no easier
than computing the optimum solution.
The PCP theorem itself doesn’t tell you
the problems for which it’s impossible
to calculate approximate solutions. But
it provided the starting point for other
results that do, and many such results
have been proved in the subsequent
two decades. And after the full body of
work, we have been able to chart the
landscape of those problems. For many
problems, we have even determined the
exact threshold of approximability: We
have algorithms that approximate it up
to some factor, and we know that doing
any better is NP-complete. Of course,
such results also sometimes involved
designing new approximation algorithms for various problems.
Let’s start with your work on the pcp
theorem, which, if i understand correctly, states that for anything you can
prove, you can write the proof in such a
way that it can be verified by looking at
only a few bits.
That’s the basic idea. The concept
was beginning to be developed just
before I started grad school. I started
working on it with some collaborators,
and that became my dissertation.
be proved using the same technique.
It’s a smaller statement, and you can
use the same ideas to give a proof
for that. Of course, this is the usual
computer science notion of “
recursion” and it increases the efficiency.
The overall procedure is algebraic.
You don’t normally think of verifying
proofs as an algebraic procedure, but
we were able to express it algebraically. This is actually quite common in
mathematics—you’re trying to prove
something about, say, knots or strings
and you encode it as an algebraic question, and from then on you can use
tools from algebra.
You helped develop some of those approximation algorithms yourself, including one for the euclidian traveling
salesman problem (tsp), a variation
of the classic np-complete problem in
which a salesman is trying to find the
shortest path by which he can visit all
of his N clients.
As I thought about the PCP theorem,
I also began wondering about whether
it was hard to compute approximate
solutions to the Euclidean TSP, which
is a classic problem. And I slowly started seeing structure in the problem that
nobody else had until that point, which
led to the algorithm.
You uncovered several key insights.
can you explain them?
One was the idea that we could
improve the efficiency of verification
by using a kind of circular reasoning.
For instance, if I’m writing a proof
that somebody else is going to verify
by looking at just a few bits, then the
statement that the verifier will accept
the proof is itself something that can
You also introduced a new definition
of np.
It was an extension of NP-complete-ness that allowed people to prove that
for certain NP-complete problems, it is
NP-complete even to compute approximate solutions. In other words, comput-
the idea sounds simple: divide and
conquer.
It’s something that people had tried
before and had given up on. Say you have
a square that encloses all the points,
and you imagine dividing the square
into subsquares. And somehow you
compute a reasonable tour within each
subsquare, and then you put them all
together. I put a twist on that idea. In the
classic divide-and-conquer scheme, you
solve each subsquare independently.
My technique was to allow a little bit of
dependence, [continUed on p. 127]