Computational theory of graphs, sets and rigid sets

Quotient spaces are a natural mathematical tool to describe a variety of algorithmic problems where different objects are to be compared while their natural symmetries are to be ignored. In particular, we will focus on graphs and sets whose symmetries are permutation of the vertices, and rigid sets whose symmetries also include rigid motions. All three data types are prevalent in computer vision/graphics, and in many other applications. 

We will discuss two problems involving these data types: (1) Geometric alignment of graphs/sets/rigid sets, and whether it can be done in polynomial time. (2) Neural network architectures which are invariant to the symmetries of graphs/sets/rigid sets, and whether they are universal (can approximate every invariant continuous function). For both problems we will see that they are tractable for sets and intractable for graphs. We will then explain why rigid sets are an intermediate case, where high dimensional rigid sets are equivalent in graphs in terms of complexity, while for fixed low dimension they are tractable. The focus on the lecture will be on two of my recent papers which leverage these insights to achieve tractable algorithms for low-dimensional rigid sets, both for geometric alignment and for invariant neural networks.