The Taub Faculty of Computer Science Events and Talks

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. Bio: Nadav Dym is an applied mathematician and computer scientist, interested in the development and analysis of algorithms, typically targeting 3D problems in computer vision and related fields. He is working on problems related to global optimization, phase retrieval, and theoretical and geometric deep learning. He is an Assistant Research Professor at the Department of Mathematics of Duke University, hosted by Prof. Ingrid Daubechies at the Information Initiative at Duke (iiD). In 2018 he completed his PhD in the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science under the supervision of Prof. Yaron Lipman. He received his BSc and MSc in mathematics from the Hebrew University.