### 3 décembre 2018

**Fabian Reiter**(IRIF)

This talk connects two classical areas of theoretical computer science:

descriptive complexity and distributed computing. The former is a branch of

computational complexity theory that characterizes complexity classes in terms

of equivalent logical formalisms. The latter studies algorithms that run in

networks of interconnected processors.

Although an active field of research since the late 1970s, distributed computing

is still lacking the analogue of a complexity theory. One reason for this may be

the large number of distinct models of distributed computation, which make it

rather difficult to develop a unified formal framework. In my talk, I will

outline how the descriptive approach, i.e., connections to logic, could be

helpful in this regard.