As a part of the NATO Security Through Science Programme, the goal of the Advanced Study Institute Physics and Computer Science was to reinforce the interface between physical sciences, theoretical computer science, and discrete mathematics.
No one can dispute the current importance of applied as well as theoretical Computer Science in the development and the practice of Physical Sciences. Physicists of course use computers in communication as well as in teaching tasks and research: software for symbolic calculus, data processing, programming, modeling and numerical simulations, learning and teaching with the aid of computers…
On the other hand, and besides the fundamental role played by mathematics in physics, methods imported from computer science are of increasing importance in theoretical physics: algorithmics, symbolic calculus, non-standard numeration systems, algebraic combinatorics, automata, cryptography… Some of them, like numeration, tilings and their associated dynamical systems, algebraic combinatorics, have already played an important role in recent developments in physics, like those accompanying the emergence of new materials (e.g. quasicrystals, uncommensurate structures) or the research around quantum information and cryptography (entanglement), or yet around quantum spin systems and related questions of integrability, and more generally in statistical physics. The intersection of combinatorics and statistical physics has been an area of great activity over the past few years, fertilized by an exchange not only of techniques but of objectives. Spurred by computing theoreticians interested in approximation algorithms, statistical physicists and discrete mathematicians have overcome language problems and found a wealth of common ground in probabilistic and algebraic combinatorics. Close connections between percolation and random graphs, between graph morphisms and hard-constraint models, and between slow mixing and phase transition have led to new results and new perspectives. These connections can help in understanding typical, as opposed to extremal, behavior of combinatorial phenomena such as graph coloring and homomorphisms. Some of the topics of particular interest are: percolation, random coloring, mixing, homomorphisms from and to fixed graph, phase transitions, threshold phenomena.
Hence, this NATO ASI School was aimed at assembling theoretical physicists and specialists of theoretical informatics and discrete mathematics in order to learn more about recent developments in cryptography, algorithmics, symbolic calculus, non-standard numeration systems, algebraic combinatorics, automata …which could reveal themselves to be of crucial interest in natural sciences. In turn, the School offered specialists in statistical physics or dynamical systems or in quantum information and quantum cryptography, or yet in new materials (e.g. quasicrystals, uncommensurate structures), the opportunity to describe aspects of their research in which new approaches imported from computer science are particularly needed.
Therefore, nearly 70 participants (students + lecturers + organizers), coming from 20 different countries (actually more than 25 nationalities), most of them being PhD students or in post-doctoral positions working in various fields, have attended courses given by 16 specialists in algorithmics, numeration systems, algebraic combinatorics, automata, languages, cryptography, quantum information, graphs and statistical mechanics.
Generally, the lectures have been introductory and pedagogical. They perfectly complied with the objective of a real transmission of knowledge between the various communities attending the Institute.
During the ten working days of the School, a total of 40 hours was reserved for lectures, and two half days were devoted to short presentations (30 or 45 min) mainly by young researchers and PhD participants. Around 35 participants presented their own research on posters displayed during the whole duration of the School. The list ofparticipants is given in the annex of this book.
Three Lectures and one concert were organized with the support of the Institut Scientifique de Cargèse:
• Roman OPALKA, Artist, France, Poland, The River of Time,
• Pierre SIMONNET, Université de Corse, Automata and games,
• Jaroslav NEŠETŘIL and Xavier VIENNOT, Arbres et Formes, Art et Mathématiques,
• Maria COLOMÉ (flute) and Jean-Yves THIBON (piano): Sonate, F. Poulenc, Sonate en si mineur, J.S. Bach.
They were aimed to attract a wide audience from Cargèse region. Moreover, the pupils of the Cargèse primary school enjoyed two pedagogical and playful presentations of the combinatorics of trees.
During the last auditorium meeting, the participants discussed important question of the relations, on a pedagogical as well as institutional level, between physics and computer science in higher education.
This volume is organized along the following rough thematic divisions:
• Chaos and Fractals,
• Quasi-Crystals and Tilings,
• Numeration, Automata, and Languages,
• Algebraic Combinatorics,
• Graphs and Networks.
This NATO-ASI “PHYSICS AND COMPUTER SCIENCE” has also been supported by l'ITI-DIMATIA, Charles University, Prague, the Collectivité Territoriale de Corse (Corsica Region), the French Ministry of Foreign Affairs, the University of Marne-La-Vallée and the GDR 673 (CNRS) “Algorithmique, Langage et Programmation”.
Jean-Pierre Gazeau, Jaroslav Nešetřil, and Branislav Rovan, Co-directors of the Advanced Study Institute Physics and Computer Science