Since the birth of ICALP and the EATCS
To highlight the 50th anniversary of the ICALP conference and of the creation of EATCS, IRIF (Institut de Recherche en Informatique Fondamentale) has set up an exhibition on 50 Years of Theoretical Computer Science: Since the birth of ICALP and the EATCS.
When first held in July 1972 at IRIA Rocquencourt near Paris, ICALP was the first conference for the newly drafted European Association for Theoretical Computer Science (EATCS). Beyond the start of a new academic venue, this was in many ways a defining moment for theoretical computer science. Through a historical tour and an overview of some key topics, the exhibition 50 Years of Theoretical Computer Science: Since the birth of ICALP and the EATCS offers a dive into this field, often way too little known.
The exhibition was first presented at ICALP’22 on July 6–8, 2022 at Université Paris Cité and then continued its tour to the Mathématiques Informatique Recherche (MIR) library from December 8, 2022 to February 27, 2023.
Designed simultaneously with the exhibition, this leaflet aims to bring the discipline and its history into the hands of all experts, curious and afficionados of theoretical computer science. Close to twenty French and international scientific contributors took part in this project, striving to share the history of the discipline and to reflect the diversity and richness of its themes. The “Further reading” sections invite the most curious to dive deeper into specific topics.
History
In the early 1970’s, computer science was generally viewed as a technology to support other enterprises, and had only recently won its autonomy as an academic discipline.
There was absolutely no appreciation of the work on the issues of computing. Mathematicians did not recognize the emerging field.
Michael Rabin
It was becoming clear however that studies were needed in order to improve the correctness and efficiency of large-scale programs. This motivated new theoretical approaches to computer science, ones that would use mathematical and logical tools to clarify and study the notion of computation. (On a more pragmatic note, this pen-and-paper endeavour had the further advantage of requiring comparably little funding, at a time when computers were massive devices whose costs could only be met by few universities.)
(CC-BY-SA 4.0, Yves Tessier, Kalos, Bibliothèque de l’Université Laval)
(© Inria / Photo Studio 9)
A theoretical computer scientist will have the same aim as any other computer scientist: namely to understand, analyze and hopefully clarify the fascinating concept of computation. The theoretical computer scientist distinguishes himself by his choice of the ways to achieve such an understanding and clarification—the choice being, after proper models have been formalised, to prove theorems that are meaningful. With the mathematician and logician, the theoretical computer scientist has in common the knowledge that sometimes the solution to a problem has to be obtained at some distance from the problem itself, and that an extensive knowledge of the relevant objects and concepts has to be developed before any major question can be answered.
Maurice Nivat
Theoretical computer science existed before the first ICALP, and that was not the first series of meetings dedicated to the topic: the annual symposium on SWitching and Automata Theory (nowadays known as IEEE FOCS) and the Symposium on Theory of Computing (ACM STOC) had been running for several years in North America. But such work in Europe tended to be local and national. Initially envisioned in an attempt to secure funding and foster collaborations among selected researchers and their institutions, the EATCS was established in September 1972 and opened to new members, growing rapidly and helping build a vibrant community through ICALP, the Bulletin of the EATCS, the journal Theoretical Computer Science, and yearly Spring schools.
Highlights
There was a very special spirit in the air; we knew that we were witnessing the birth of a new scientific discipline centered on the computer.
Richard Karp
Maurice Nivat, Louis Nolin, and Marcel-Paul Schützenberger outlined the main pillars of the new scientific discipline in their Rapport préliminaire sur l’informatique théorique, and even held a press conference announcing the birth of theoretical computer science.
The original vision revolved around three main areas: algorithms and complexity, automata and formal languages, and programming languages. These core topics have grown considerably in scope and in depth since 1971, and have found wide-ranging impact on the real world.
Theoretical computer science has also spawned into many new directions: distributed computing, databases, machine-checked proofs, quantum computing, cryptography, machine learning, model-checking, etc.
Special Thanks
Special thanks to all the people involved into creating this exhibition.
Coordination
Sandrine Cadet (IRIF, Université Paris Cité), Sylvain Schmitz (IRIF, Université Paris Cité)
Scientific Advisory Board
Luca Aceto (Reykjavik University), Susanne Albers (Technische Universität München), Giorgio Ausiello (Sapienza University of Rome), Gilles Dowek (ENS Paris-Saclay), Phokion G. Kolaitis (UC Santa Cruz), Mike Paterson (University of Warwick), Sylvain Schmitz (IRIF, Université Paris Cité)
Additional Contributors
Simon Apers (CNRS), Alex Bredariol Grilo (LIP6, CNRS, Sorbonne Université), Ioannis Catzigiannakis (Sapienza University of Rome), Geoffroy Couteau (CNRS), Pierluigi Crescenzi (Gran Sasso Science Institute, L’Aquila), Irène Guessarian (IRIF, Université Paris Cité), Hugo Herbelin (Inria, IRIF), Ce Jin (MIT), Jean-Jacques Levy (Inria, IRIF, CNRS), Kurt Melhorn (Max-Planck-Institut für Informatik), Subhasree Patro (QuSoft, CWI Amsterdam), Sylvain Périfel (IRIF, Université Paris Cité), Jean-Éric Pin (IRIF, CNRS)
Co-organizers
Partners
CONTACT US
icalp2022@irif.fr
@ICALPconf