בניין מדעי המחשב

NADAV DYM

DUKE University

ירצה על

Will lecture on

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. 

Zoom link:  

https://us02web.zoom.us/j/83383478356