2019/2020 Edition

Symmetric Computation

Anuj Dawar (University of Cambridge).


Course Summary | About the lecturer | Location and schedule | Materials | Videos

Course summary:

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, I will present the various symmetric models introduced in these fields and establish their close relationship. I 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.

About the lecturer:

Anuj Dawar is Professor of Logic and Algorithms at the University of Cambridge, where he has been a member of the faculty since 1999. He obtained a Bachelor's degree from IIT, Delhi and a Master's degree from the University of Delaware before going on to get his PhD from the University of Pennsylvania in 1993. Before coming to Cambridgehe worked for several years as a post-doc and a lecturer at Swansea University.

Professor Dawar has an interest in computational complexity theory, which seeks to understand the fundamental limitations of some of our most powerful algorithmic techniques. He has worked for many years on approaches to complexity based on logic - by relating computational complexity to problems of definability. Recently he has been focusing on the role of symmetry in computation, both as a resource and a limitation.

Location and schedule:

MIMUW, room 5440.

Thursday, October 17
14:15 - 15:45 lecture
15:45 - 16:00coffee and cake
16:00 - 17:00 class
Friday, October 18
14:15 - 15:45 lecture
15:45 - 16:00 coffee and cake
16:00 - 17:00 class
Saturday, October 19
10:00 - 10:15 coffee and cake
10:15 - 11:45 lecture
11:45 - 12:00 coffee and cake
12:00 - 13:00 class

Materials