Complexity Theory of Interactive Computing

(1990-1991)

Michael Luby (International Computer Science Institute)

Noam Nisan (Interdisciplinary Center Herzliya)

February 5, 1998

When asked about the 1990-91 Special Year on Complexity Theory of Interactive Computation, most participants spout out a five letter response: FGLSS. The letters refer to the authors of perhaps the most in influential paper in theoretical computer science during the 90's. To understand the impact of this paper, it is useful to recall the state of knowledge of Theoretical Computer Science in 1990.

In the early 1970's, Steve Cook and Richard Karp (and independently, Leonid Levin in Russia) introduced the theory of NP-completeness. This theory provides the foundation of modern day Theoretical Computer Science: it gives a general scientific basis for classifying a problem as hard to solve exactly, and shows that a large number of natural problems fall into this classification. This opened the way for thousands of subsequent researchers to be able to classify thousands of problems as hard to solve exactly. However, this was also in some sense a point of divergence between Theoretical Computer Science and practitioners: in practice, a problem that can't be solved exactly still needs to be solved, at least

With a sheer stroke of genius, in one paper FGLSS introduced the scientific framework for a general theory of hardness of approximation, and showed that it was as hard to approximate some natural problems as it is to find an exact solution. With further refinements in the theory by an army of researchers, the theory of approximation hardness has now progressed to the point that it provides a solid basis for concluding that it is hard to even slightly approximate a wide range of natural problems.

The most amazing fact regarding this paper is the technique: the hardness of approximation was derived as a direct corollary from the most recent results regarding interactive proofs - the subject of the DIMACS special year. This very surprising connection still serves as the main tool driving both the field of interactive proofs and the field of approximation algorithms.

The paper represents the ideal of the DIMACS model in terms of its combination of authors, bringing together far flung researchers under a common theme: Uriel Feige, a postdoc after receiving his doctorate at The Weizmann Institute in Israel; Shafi Goldwasser, an MIT professor visiting DIMACS, Laszlo Lovasz from Princeton and Eotvos University in Hungary, Shmuel Safra an MIT postdoc visiting DIMACS. Mario Szegedy, a visiting professor at the University of Chicago, joined the collaboration with research starting at a workshop during the special year.

Because of the importance of this paper we devote much of this report to describing the result and its impact (see Section 2). The special year was successful by many other measures such as some well attended workshops and useful collaborations. We discuss some of these other aspects in Section 3.

Garey and Johnson, in their book on NP-completeness [GJ79], tell a story of an algorithm programmer told by his boss to find the optimal design for ``bandersnatches''. The book goes on to tell how this programmer can use the fact that the problem is NP-complete to convince his boss that the best way to find the optimal bandersnatch design is to look through all the possibilities - an impractically slow solution.

The story could have gone on to have the boss say he will settle for a nearly optimal solution. Most likely the programmer would have gone back to attempt this, but after hitting his head against the wall for a few days, would have gone back to his boss to report his failure. Unfortunately, if this story occurred before 1990, the programmer could not give his boss any convincing evidence that there was little possibility of a near optimal solution (other than the fact that he failed to find one), and thus the boss would most likely have fired him. With the breakthroughs initiated by FGLSS, the programmer would once again be in good shape: he would be able to convince his boss that the best way to find even an approximation to the optimal bandersnatch design is to look through all the possibilities.

The breakthroughs discovered at the DIMACS special year now give us a systematic way to show that large classes of problems cannot be approximable unless we can solve them exactly. The results during the special year already helped classify the hardness of approximation of a large group of problems. In the seven years hence, we have seen an explosion of research improving these results and showing hardness bounds for most of the well known NP-complete search problems.

Quite surprisingly, these hardness results, encouraged positive results as well. Recently we have seen some new approximation schemes for some problems such as traveling salesperson on the plane [Aro96, Aro97]. These approximation algorithms were obtained after the failure of the author in proving the required hardness results.

What does the hardness of approximation have to do with ``The Complexity Theory of Interactive Computation?''. On the face very little, but in fact results on interactive computation have many surprising applications to showing a wide variety of hardness results for approximating search problems. This connection, discovered at the DIMACS special year, showed a far greater applicability of interactive computing than anyone previously believed.

While visiting the special year at DIMACS, Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra and Mario Szegedy [FGL+96] made an amazing connection between interactive proof systems and approximating the largest clique. They realized that the sets of consistent computations for the verifier of certain interactive proof systems would form either large or small cliques depending on whether there is a successful prover. Combining this technique with recent results on interactive proof systems [LFKN92, Sha92, BFL91] showed that if an efficient approximation algorithm for clique existed, some unbelieved collapses of complexity classes occurs.

The result by FGLSS started a larger research program settling the hardness of approximation question of many important problems.

The next major steps were obtained by Sanjeev Arora and Muli Safra [AS92] and by Carsten Lund and Mario Szegedy working with Sanjeev Arora, Rajeev Motwani and Madhu Sudan [ALM+92] who introduced and analyzed Probabilistically Checkable Proofs (PCPs). These results extended the connection discovered in FGLSS between proof systems and hardness of approximation and combined it with recent work in program testing [BLR93], yielding better proof systems, program testing and hardness of approximation results.

Arora, Lund et. al. showed that every problem in NP has a PCP system that uses only

In fact, the PCP result gives hardness results for a large class of approximation problems. Papadimitriou and DIMACS member Mihalis Yannakakis [PY91] noticed that many approximation problems have a similar structure and called this class MAX-SNP. The class MAX-SNP contains many important approximation questions such as maximizing the number of satisfiable clauses in a formula or finding the largest independent set in a graph.

Soon thereafter, DIMACS members Lund and Yannakakis [LY94] showed how to apply and extend the PCP results to the hardness of minimization problems such as graph coloring and set covering. Johan Hastad [Has97] later found optimal lower bounds on the approximation of certain search problems.

These results started a floodgate of research into PCPs and their applications to the hardness of approximation problems. Much research went into tightening the PCP results, usually by improving the low-degree polynomial test within leads to better bounds on approximation. Also we have seen the results applied to more and more approximation problems.

DIMACS remains a leader in the hardness of approximation problems area with Arora, Lund, Yannakakis, Joan Feigenbaum and Peter Shor currently having permanent jobs in DIMACS member institutions.

The amount of research devoted to these questions would fill several books. At an Israeli workshop on PCPs in 1994, a bibliography of 155 papers relating to PCPs was put together. The Hypertext Bibliography Project lists nearly a hundred papers referencing Arora, Lund, et. al.

We cannot mention even a small fraction of the work devoted to these problems here. We would like to quickly mention two recent results that show the continuing use of the ideas developed during at DIMACS during the special year.

Johan Hastad [Has97] shows optimal lower bounds on the approximation of certain search problems such as satisfying the largest number of clauses of a 3CNF formula. For this problem, a simple algorithm based on a randomized approach yields an approximation of 7/8. Hastad shows that no algorithm can achieve an approximation value

He achieves this goal by once again using the connection between interactive proof systems and approximation developed by Feige, et. al. Hastad uses some new results on parallelization of interactive proof systems by Raz [Raz95] to improve upon the earlier techniques to prove hardness results.

Sanjeev Arora [Aro96, Aro97] found new algorithms to give good quick approximation schemes for solving traveling salesperson on the plane. Very surprisingly, he combines known standard techniques in ingenious ways to solve one of the most famous and long standing open problems. It was the failure of his attempts to prove that this problem was hard to approximate that gave Arora the confidence and stamina that allowed him to find his beautiful algorithms.

Besides the results described above, the special year was successful in many other aspects.

While the highlight of the year goes to FGLSS, several other exciting research results arose from the special year. This report does not have the space to mention them all. We will mention a couple in this section.

In the couple of years before the special year, great strides have been made in theoretical program checking and correction bringing us new robust definitions and some exciting results [BK89, BLR93]. One line created self-testers and correctors for multivariate low-degree polynomials. However their techniques seem to require that the program computes these polynomials exactly. During the special year, DIMACS participants Richard Lipton, Ronitt Rubinfeld and Avi Wigderson with Peter Gemmel and Madhu Sudan from Berkeley showed how to create self-testers and correctors even if the program only computer approximations to the polynomials [GLR+91].

Decisions trees provide interesting models of computation where we measure the complexity of a problem based on the number of queries need to solve it. DIMACS participants Laszlo Lovasz, Ilan Newman and Avi Wigderson, together with Moni Naor of IBM Almaden give strong separations for search problems in the deterministic, randomized and nondeterministic decision tree models [LNNW91].

Participants of the special year make a special point to mention the interactions with other participants. These connections led to some of the great results described above and continue to produce strong research to this day. Many of these collaborations are described in Section 2.

The collaborations go far beyond those working on approximation results. DIMACS participants Avi Wigderson and Endre Szemeredi with Noam Nisan showed that undirected connectivity requires only

Many of the postdocs supported during the special year have gone on to very productive research careers. This list includes Uri Feige, Rafi Heiman, Sampath Kannan, Carsten Lund, Ilan Newman and Ronitt Rubinfeld.

DIMACS hosted several workshops during the special year. These meetings brought together many of the best researchers in the area in different areas relating to the theme of the year.

The year started off with a workshop on cryptography. The meeting had many presentations on new research on interactive proof systems, program testing and quantum computing. Joan Feigenbaum and Michael Merritt produced a book [FM91] containing work from many of the participants.

In December, DIMACS hosted a workshop on Structural Complexity and Cryptography. At the time, we were just feeling the strong connections between these areas and this workshop brought together the best researchers who were finding connections in these areas.

In the spring, DIMACS also had well-attended workshops on Circuit and Communication Complexity and Computational Number Theory.

Perhaps the only disappointment of the special year was in Computational Learning Theory which was one of the topics mentioned in the proposal but never materialized into a major part of the special year.

By any other measure, the special year was a huge success. It had ground breaking research, brought many of the best researchers together and hosted four important workshops. This year really showed off the advantages of the DIMACS model and its ability to produce great advances in science.

[ALM+92] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In

[Aro96] Sanjeev Arora. Polynomial time approximation scheme for Euclidean TSP and other geometric problems. In

[Aro97] Sanjeev Arora. Nearly linear time approximation scheme for Euclidean TSP and other geometric problems. In

[AS92] S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. In

[BFL91] L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols.

[BK89] M. Blum and S. Kannan. Designing programs that check their work. In

[BLR93] M. Blum, M. Luby, and R. Rubinfeld. Self-testing and self-correcting programs, with applications to numerical programs.

[FGL+96] U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques.

[FL92] Uriel Feige and Carsten Lund. On the hardness of computing the permanent of random matrices (extended abstract). In

[FM91] J. Feigenbaum and M. Merritt, editors. Distributed Computing and Cryptography, volume 2 of

[GJ79] M. Garey and D. Johnson. Computers and intractability.

[GLR+91] P. Gemmel, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self testing / correcting for polynomials and for approximate functions. In

[Has97] J. Hastad. Some optimal inapproximability results. In

[LFKN92] C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems.

[LNNW91] L. Lovasz, I. Newman, M. Naor, and A. Wigderson. Search problems in the decision tree model. In

[LY94] C. Lund and M. Yannakakis. On the hardness of approximating minimization problems.

[NSW92] N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in

[PY91] C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes.

[Raz95] R. Raz. A parallel repetition theorem. In

[Sha92] A. Shamir. IP = PSPACE.

DIMACS home page

Contacting the Center

Document last modified on May 1, 1998.