Gazeau J.-P., Nešetřil N., Rovan B. (eds.) Physics and Theoretical Computer Science. From Numbers and Languages to (Quantum) Cryptography

IOS Press, 2007, -348 p.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, nonstandard 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 Ph.D. 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 Ph.D. participants. Around 35 participants presented their own research on posters displayed during the whole duration of the School. The list of participants is given in the annex of this book.Mathematical Aspects of Quantum Information Theory
Dynamical Symmetry Approach to Entanglement
Mathematics of Phase Transitions
The Topology of Deterministic Chaos: Stretching, Squeezing and Linking
Random Fractals
Quasicrystals: Algebraic, Combinatorial and Geometrical Aspects
Pisot Number System and Its Dual Tiling
Non-Standard Number Representation: Computer Arithmetic, Beta-Numeration and Quasicrystals
An Introduction to the Theory of Finite Transducers
Generating Languages
Basic Enumerative Combinatorics
An Introduction to Noncommutative Symmetric Functions
An Introduction to Combinatorial Hopf Algebras — Examples and Realizations
Complex Networks: Deterministic Models
Homomorphisms of Structures Concepts and Highlight
Some Discrete Tools in Statistical Physics