Symmetric Computation

Anuj Dawar and Gregory Wilsenach

Abstract

The notion of a symmetric algorithm, i.e. one with an explicit combinatorial property that guarantees isomorphism-invariant computation, arises naturally in the context of database theory, finite model theory, circuit complexity, the theory of relational machines, and theory of linear programming. The apparently very different models of symmetric computation developed in these disparate fields have recently been shown to be closely related both in terms of expressive power and underlying theory. The set of ideas that emerge in all of these cases have coalesced into a coherent and robust theory of symmetric computation.

This course will introduce this exciting and emerging new theory. In particular, we will present the various symmetric models introduced in each of these fields and establish their close relationship. We will develop the common theory and the methods for proving upper and lower bounds on expressive power. These rest on the Weisfeiler-Leman equivalences, the related notion of counting width, and logical reductions. Lastly, we will discuss extensions of these models and a number of open questions.

Details

This advanced course is part of ESSLLI 2021 (postponed from 2020) and is scheduled to take place from August 9th to August 13th 2021. The course uses the “flipped classroom” style. That is, it consists of five prerecorded lectures, each approximately an hour and a half long, with corresponding live discussion sessions at 4pm daily (CEST). These sessions are intended to last between 40-60 minutes, and will consist of a short talk expanding on some of the important topics covered in the lecture before continuing on to a more open forum.

The prerecorded lectures, slides and notes for the discussion sessions are all available from the adjacent menu. For more details on the ESSLLI schedule see here and for the ESSLLI page on this course please see here.