Sponsored by:

Association for Computing Machinery - SIGSAM

Invited Speakers

Titles and Abstracts

Nikhil Srivastava
UC Berkeley, USA


Abstract: TBA

Rekha R. Thomas
University of Washington, USA

Classical Invariant Theory in Computer Vision

Abstract: Invariant theory arises naturally in reconstruction problems in computer vision because most common models of cameras are defined up to some group action. In this talk I will explain some fundamental questions that arise in the reconstruction of 3d scenes from images in two cameras, where the invariant theory of point sets in the projective plane play a major role. They come hand in hand with classical constructions in algebraic geometry such as cubic surfaces and their 27 lines and related objects.

Frank Vallentin
Universität zu Köln, Germany

Least Distortion Euclidean Embeddings of Flat Tori

Abstract: Lattices (discrete subgroups of $n$-dimensional Euclidean spaces) are ubiquitous objects in mathematics.

One typical algorithmic problem for lattices is the closest vector problem (given a lattice and a point in Euclidean space, which lattice vector is closest to this given point?). In general the closest vector problem is NP-hard. One potential approach to derive efficient approximation algorithm the closest vector problem could go via the concept of least distortion metric embeddings.

In this talk I will derive and analyze an infinite-dimensional semidefinite program which computes least distortion embeddings of flat tori $R^n/L$, where $L$ is an $n$-dimensional lattice, into Hilbert spaces. This enables us to provide a very simple, constant factor improvement over the previously best known lower bound on the minimal distortion of an embedding of an $n$-dimensional flat torus. As further applications we prove that every $n$-dimensional flat torus has a finite dimensional least distortion embedding, and we derive some optimal embeddings of flat tori given by certain important lattices.