[Facets-of-complexity] Invitation and link to Monday Lecture - December 7th 2020 - online via zoom

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture. Next Monday, there will be the hearing of the PhD candidates.

We will have three talks. Talks will be 30 min. 15 min discussions, 15 min break.
All Monday Lectures and Colloquia of winter term 2020/21 will be given online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on December 7th 2020 at 14:00 h, 15:00, 16:00.

Online via:
Zoom - Invitation

Time: Monday, December 7th - 14:00 h

Lecture: Hussein Houdrouge

Title: Subquadratic High-Dimensional Hierarchical Clustering

Abstract:

We consider the widely-used Ward's method for computing hierarchical clusterings of high-dimensional Euclidean inputs. It is easy to show that there is no ecient implementation of these algorithms in high dimensional Euclidean space since it implicitly requires to solve the closest pair problem, a notoriously dicult problem. However, how fast can this algorithm be implemented if we allow approximation? More precisely: this algorithm successively merges the clusters that are at inducing the least sum-of-square error. We ask whether one could obtain a signicant running-time improvement if the algorithm can merge -approximate closest clusters (namely, clusters that are at distance sumof-square error at most times the distance of the closest clusters). We show that one can indeed take advantage of the relaxation and compute the approximate hierarchical clustering tree using -approximate nearest neighbor queries.
This leads to an algorithm running in time ~O (dn) + n1+O() for d-dimensional Euclidean space. We then provide experiments showing that this algorithm performs as well as the non-approximate version for classic classication tasks while achieving a signicant speed-up.

Time: Monday, December 7th - 15:00 h

Lecture: Kemal Rose

Title: tba

Abstract:

tba

Time: Monday, December 7th - 16:00 h

Lecture: Filippos Christodoulou

Title: tba

Abstract:

tba