The Joy of Theory

ABSTRACT

This talk is meant to be a celebration of theoreticians, thier achievements, and thier unique style, drawing to a large extent on examples from this volume.Theoretical Computer Science has largely succeeded in its core mission, that is, improving a rigorous and productive foundational understanding of the power and limitations of the von Neumann computer and its software. And in the past few years it has strived to extend its reach to the Internet and the worldwide web, the central computational artifact of our times.But theoreticians have achieved much more than this. Our community has identified P vs. NP, arguably the deepest and most important mathematical question of our time -- and it is leading the assault on it. In addition we are developing "algorithmic mirrors" through which other sciences (notably Physics and Biology, with Economics and other Social Sciences soon to join) rediscover, fruitfully, themselves. And we have furthered and influenced crucially Combinatorics and Logic, the important mathematical fields from which we have drawn methodologically. The newfound respectability and prestige of our parent field, Computer Science, owes much to these achievements.Theoreticians comprise a microcosm with wonderful characteristics: Great scientific, social, and intellectual openness; responsibility and mutual respect, but also healthy doses of irreverence, mistrust of the establishment, willingness to experiment, and self-critical spirit; and a strong sense of an international community that is remarkably cohesive and tightly knit while celebrating the diversity of its people, of their backgrounds, and of their scientific interests and approaches.We have also developed a fascinating, complex esthetic of our work based on mathematical elegance and depth, relevance and fashion, timeliness and competition -- but also on playfulness and humor. Our esthetic has served us well: Some of our most important results were derived by long chains of contributions, each seemingly guided to a large extent by such esthetic considerations. In fact, this esthetic extends delightfully to the exposition of our work, as evidenced by the unique genre of scientific prose known as "FOCS/STOC abstract".

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic
      F.4.3 Formal Languages
          Subjects: Decision problems

General Terms:
Design, Measurement, Performance, Theory