Communications of the ACM

Last byte

Q&A: As Good As It Gets

By Leah Hoffmann
Communications of the ACM, December 2012, Vol. 55 No. 12, Pages 128-ff
10.1145/2380656.2380681
Comments

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 probabilistically 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.

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.

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 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 also introduced a new definition of NP.

It was an extension of NP-completeness that allowed people to prove that for certain NP-complete problems, it is NP-complete even to compute approximate solutions. In other words, computing 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.

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.

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, 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-optimum solution, and there's a simple dynamic programming language that enables you to compute the tour with these restrictions.

You've also worked on the use of semidefinite programming, an extension of linear programming that was developed in the 1980s, in approximation algorithms.

Semidefinite programming gives a very general methodology for computing approximate solutions to NP-complete problems. First, you try to relax the problem—meaning that you create an intuitive approximation by throwing away some features—such that it can be represented by a linear or semidefinite program. Then you solve that program.

So semidefinite programming can be used to find approximations for many NP-complete problems.

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 formulated by your former student Subhash Khot about the difficulty of assigning colors to the vertices of a network.

The UGC has a very interesting connection to semidefinite programming because it seems to imply that for many problems, semidefinite programming is the best way to approximate the problem. So, in fact, it can be shown that if the semidefinite program doesn't work, then no other technique works. My research is just a small part of that; many other people were involved.

Your recent work with Boaz Barak and David Steurer proved the existence of a subexponential algorithm for the UGC. What are the implications of that discovery?

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 Intractability.

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 research that has come out of your work with the center?

The above work on UGC is one. Another 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 problems that were connected with them seemed to be intractable problems. So some colleagues and I started discussing it. In economic theory, it turns out, there are various justifications for derivatives. 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.

How?

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 improved modeling.

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.

---

No entries found