INF631 -- Exam

You must gather into groups of 2 people (singletons will be accepted only in special situations), then choose exactly one paper per group within the list of 8 papers (2 per topic) below. Please note that each paper must be chosen by at most a single group. Once your choice has been made, you can report it on the dedicated Doodle (first come first serve).

Nearest neighbor search

• Vempala: Randomly-oriented kd Trees Adapt to Intrinsic Dimension. FSTTCS, 2012. [pdf]
• Andoni, Indyk, Nguyen, Razenshten: Beyond Locality-Sensitive Hashing. SODA, 2014. [pdf]

Delaunay-based reconstruction

• Boissonnat, Ghosh: Manifold reconstruction using tangential Delaunay complexes. DCG, 2014. [pdf]
• Lederer, Wang, Gao: Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape. ToSN, 2009. [pdf]

Metric clustering

• Carlsson, Mémoli: Persistent Clustering and a Theorem of J. Kleinberg. ArXiv:0808.2241, 2008. [pdf]
• Chepoi, Fichet: l^\infty-Approximation via Subdominants. Journal of Mathematical Psychology, 2000. [pdf]
• Huang, Fu, Sidiropoulos: On Convergence of Epanechnikov Mean Shift. AAAI, 2018. [pdf]

Topological inference

• Hofer, Kwitt, Niethammer, Uhl: Deep Learning with Topological Signatures. NIPS 2017. [pdf]
• R. Gabrielsson, G. Carlsson: Exposition and Interpretation of the Topology of Neural Networks. Preprint, 2019. [pdf]
• M. Carrière, F. Chazal, Y. Ike, T. Lacombe, M. Royer, Y. Umeda: PersLay: A Simple and Versatile Neural Network Layer for Persistence Diagrams. Preprint, 2019. [pdf]

Your task is to read and understand the paper in depth (even if not in full). In particular, you should focus on its goals, challenges, proposed methods, guarantees, experimental results, and limitations, as we did during the exercise sessions. Remember not to lose time on insignificant aspects. Quality will be judged by three main criteria:

• how well you have succeeded at grabbing the main points of the paper;
• how deep your understanding is of the method, of its strengths and limitations;
• how far beyond the paper you have managed to go, either on the theory side or on the experimental side.

On defence day you must deliver a 20-minutes talk with slides and be prepared for a 25-minutes long discussion. The total duration of the defence will be 45 minutes. No written report is expected.