Report on DIMACS Special Year on
Complexity Theory of Interactive Computing
(1990-1991)
Lance Fortnow, Chair (University of Chicago)
Michael Luby (International Computer Science Institute)
Noam Nisan (Interdisciplinary Center Herzliya)
February 5, 1998
1 Building Bridges
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 approximately. The theory of NP-completeness
had almost nothing to say regarding approximate solutions. Thus, as of 1990, for a large number of
natural problems there was no known efficient approximation algorithm, and yet there was also
no scientific evidence to conclude that no such algorithm exists.
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.
2 Approximation Results
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.
2.1 Proof Systems, Program Checking and Hardness of Approximation
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.
2.2 Continuing Research
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 O(log n)
random coin and a constant number of queries to the proof. While interesting in its own right this
result also gives important results on approximation for search problems. For example these
results show that for some E > 0, clique cannot be approximated by a factor of nE unless P = NP.
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.
2.3 Current Research
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 p > 7/8 unless P = NP.
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.
3 The Rest of the Special Year
Besides the results described above, the special year was successful in many other aspects.
3.1 Other Research
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].
3.2 Collaborations and Training
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 O(log1.5n) space breaking the two decade old O(log2n) barrier [NSW92]. DIMACS
participants Uri Feige and Carsten Lund showed the unlikeliness of computing the permanent on
even a tiny fraction of matrices [FL92].
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.
3.3 Workshops
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.
4 Conclusions
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.
References
[ALM+92] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and
hardness of approximation problems. In Proceedings of the 33rd IEEE Symposium on
Foundations of Computer Science, pages 14-23. IEEE, New York, 1992.
[Aro96] Sanjeev Arora. Polynomial time approximation scheme for Euclidean TSP and other
geometric problems. In Proceedings of the 37th IEEE Symposium on Foundations of Computer
Science, pages 2-11, New York, 1996. IEEE.
[Aro97] Sanjeev Arora. Nearly linear time approximation scheme for Euclidean TSP and other
geometric problems. In Proceedings of the 38th IEEE Symposium on Foundations of Computer
Science, pages 554-563, New York, 1997. IEEE.
[AS92] S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of
NP. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 2-13. IEEE, New York, 1992.
[BFL91] L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover
interactive protocols. Computational Complexity, 1(1):3-40, 1991.
[BK89] M. Blum and S. Kannan. Designing programs that check their work. In Proceedings of
the 21st ACM Symposium on the Theory of Computing, pages 86-97. ACM, New York, 1989.
[BLR93] M. Blum, M. Luby, and R. Rubinfeld. Self-testing and self-correcting programs, with
applications to numerical programs. Journal of Computer and System Sciences, 47:549-595,
1993.
[FGL+96] U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Interactive proofs and
the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, March 1996.
[FL92] Uriel Feige and Carsten Lund. On the hardness of computing the permanent of random
matrices (extended abstract). In Proceedings of the 24th ACM Symposium on the Theory of
Computing, pages 643-654. ACM, New York, 1992.
[FM91] J. Feigenbaum and M. Merritt, editors. Distributed Computing and Cryptography,
volume 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
American Mathematical Society, Providence, 1991.
[GJ79] M. Garey and D. Johnson. Computers and intractability. A Guide to the theory of
NP-completeness. W. H. Freeman and Company, New York, 1979.
[GLR+91] P. Gemmel, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self testing /
correcting for polynomials and for approximate functions. In Proceedings of the 23rd
ACM Symposium on the Theory of Computing, pages 32-42. ACM, New York, 1991.
[Has97] J. Hastad. Some optimal inapproximability results. In Proceedings of the 29th ACM
Symposium on the Theory of Computing, pages 1-10. ACM, New York, 1997.
[LFKN92] C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive
proof systems. Journal of the ACM, 39(4):859-868, 1992.
[LNNW91] L. Lovasz, I. Newman, M. Naor, and A. Wigderson. Search problems in the decision
tree model. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science,
pages 576-585. IEEE, New York, 1991.
[LY94] C. Lund and M. Yannakakis. On the hardness of approximating minimization problems.
Journal of the ACM, 41(5):960-981, September 1994.
[NSW92] N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in O(log1.5n)
space. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages
24-29. IEEE, New York, 1992.
[PY91] C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity
classes. Journal of Computer and System Sciences, 43:425-440, 1991.
[Raz95] R. Raz. A parallel repetition theorem. In Proceedings of the 27th ACM Symposium on
the Theory of Computing, pages 447-456. ACM, New York, 1995.
[Sha92] A. Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, 1992.
DIMACS home page
Contacting the Center
Document last modified on May 1, 1998.