Piotr Indyk: "Algorithms for Geometric Search Problems"

        

Abstract:

 

Similarity search in large collections of high-dimensional geometric data is a notoriously difficult yet fascinating computational problem. In this talk I will present an overview of old and new algorithms for this problem, with the emphasis on methods based on "Locality-Sensitive Hashing".

 

Herbert Edelsbrunner: “Biology and Topology”

 

Abstract:

 

The terminology we find in the two fields, such as `homology',   `complexes', `networks', `functions', betray a deep connection. Perhaps the reason are common or similar objects under study,  but we believe the connection runs deeper.  While the reductionist  approach generated breath-taking insights in biology during last  century, it is becoming clear that things are intertwined and  related in a major way and along many axes, space, time, and scale including.  Topology is at its best when it comes to global properties arising from integrating local phenomena into a whole. This is needed in biology today, methods that allow us to reason about the system based on how its parts behave and are put together.

 

Jean Ponce: “Geometry and 3D computer vision: What we (kind of) know how to do, what we don't, and why anyone should care”

 

Abstract:

 

I will present my views on the role of geometry in computer vision, a  domain concerned with the automated interpretation of digital imagery. I will focus on two challenging problems, namely the acquisition of  three-dimensional (3D) object and scene models from multiple pictures --- a process known as 3D photography, and the

identification of previously observed objects (or object categories) in new images --- a process known as object recognition. In the first part of the talk, I will show that an essential part of the relationship between the shape of solids bounded by smooth surfaces amd their image outlines is inherently projective. This observation leads to a better qualitative understanding of the image formation process, as well as effective image-based algorithms for high-fidelity 3D photography. In the second part of my presentation, I will argue that object recognition is probably the most challenging and exciting problem in computer vision today, but that, despite exciting recent progress, several key representational issues (including, but not limited to, geometric ones) have yet to be addressed. I will illustrate this point by discussing some recent results and open issues. I will conclude with a discussion of potential applications of 3D photography and object recognition to non-traditional domains such as archaeology, anthropology, cultural heritage preservation, film post-production and special effects, and forensics. Joint work with Yasutaka Furukawa, Akash Kushal, Svetlana Lazebnik, Kenton McHenry, Fred Rothganger, and Cordelia Schmid.

 

Ravi Kannan: ”Random Sampling in Massive Data Matrices and Tensors“

 

Abstract:

 

The talk will survey a body of recently developed results to deal with massive data in the form of matrices and tensors that arise in many modern applications. The general gist is that if one picks a sub-matrix of the input matrix at random. then indeed Linear Algebra can be carried out on the random sample instead of the whole matrix. The key will be a simple, judicious choice of probability distribution to do the random sampling.  The methods are extended to tensors. Besides the tradtional applications such as Principal Component Analysis, these results can also be used to solve approximately a class of combinatorial optimization problems.