Descriptive distributed complexity

December 3, 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.