Arnaud Casteigts
Professeur, LABRI, Université de Bordeaux
https://www.labri.fr/perso/acasteig/
“Introduction to computational complexity and distributed algorithms”
In this talk, I will give a brief introduction to two areas of theoretical computer science. The first is computational complexity, where the goal is to understand how much resources (in time or space) are needed to solve a given problem. The most famous question in this area is certainly the P versus NP question. The second part will briefly present the field of distributed algorithms, which studies how several entities may interact in order to solve a common problem in absence of central authority. Covering each of these fields in less than half an hour is of course impossible, the goal is merely to give some ideas of the type of questions computer scientists study in such fields, some of which are certainly related to questions in physics.