Preface

Proof Verification and Approximation Algorithms - Hardly any area in theoretical computer science has been more lively and flourishing during the last few years. Different lines of research which had been developed independently of each other over the years culminated in a new and unexpected characterization of the well-known complexity class NP, based on probabilistically checking certain kinds of proofs. This characterization not only sheds new light on the class NP itself, it also allows to prove non-approximability results for optimization problems which, for a long time, had seemed to be out of reach. This connection, in turn, has motivated scientists to take a new look at approximating NP-hard problems as well - with quite surprising success. And apparently, these exciting developments are far from being finished.

We therefore judged "Proof Verification and Approximation Algorithms" an ideal topic for the first in a new series of research seminars for young scientists, to be held at the International Conference and Research Center for Computer Science at Schloß Dagstuhl in Germany. This new series of seminars was established by the German Society for Computer Science (Gesellschaft für Informatik, GI) with the aim of introducing students and young scientists to important new research areas and results not yet accessible in text books or covered in the literature in a comprehensive way.

When we announced our seminar we encountered considerable interest and received numerous responses. We were able to select 21 qualified doctoral students and postdocs. Each participant then was requested to give a lecture, usually based on several research articles or technical reports, and to submit, in preliminary form and before the workshop began, an exposition of the topic assigned to him/her. The actual workshop then took place April 21-25, 1997 at Schloß Dagstuhl. All participants were very well prepared and highly motivated. We heard excellent talks and had many interesting and stimulating discussions, in the regular sessions as well as over coffee or some enlightening glass of wine after dinner.

This volume contains revised versions of the papers submitted by the participants. The process of revision involved, among other things, unifying notation, removing overlapping parts, adding missing links, and even combining some of the papers into single chapters. The resulting text should now be a coherent and essentially self-contained presentation of the enormous recent progress facilitated by the interplay between the theory of probabilistically checkable proofs and approximation algorithms. While it is certainly not a textbook in the usual sense, we nevertheless believe that it can be helpful for all those who are just starting out to learn about these subjects, and hopefully even to those looking for a coherent treatment of the subject for teaching purposes.

Our workshop was sponsored generously by Special Interest Group 0 (Fachbereich "Grundlagen der Informatik") of the German Society for Computer Science (GI) and by the International Conference and Research Center for Computer Science (Internationales Begegnungs- und Forschungszentrum für Informatik, IBFI) at Schloß Dagstuhl. We owe them and the staff at Schloß Dagstuhl many thanks for a very successful and enjoyable meeting.

München, Berlin
September 1997

Ernst W. Mayr
Hans Jürgen Prömel
Angelika Steger