Computational Geometry and Topology -- Exam
You must choose one paper within the list below. Please note that each paper must be chosen by at most one person. Once your choice has been made, you must report it on the dedicated poll (first come first serve) before October 1st.
Nearest neighbor search
- Dasgupta, Freund: Random Projection Trees for Vector Quantization. IEEE Transaction on Information Theory, 2009 [pdf]
- Vempala: Randomly-oriented kd Trees Adapt to Intrinsic Dimension. FSTTCS, 2012. [pdf]
- Andoni, Indyk, Nguyen, Razenshten: Beyond Locality-Sensitive Hashing. SODA, 2014. [pdf]
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]
- Attali, Lieutier, Salinas: Efficient Data Structure for Representing and Simplifying Simplicial Complexes in High Dimensions. IJCGA, 2012. [pdf]
- Dey, Fan, Wang: Graph Induced Complex on Point Data. CGTA, 2015. [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]
Persistent homology
- Bauer, Kerber, Reininghaus: Clear and Compress: Computing Persistent Homology in Chunks. TopoInVis, 2014. [pdf]
- de Silva, Morozov, Vejdemo-Johansson: Dualities in persistent (co)homology. Inverse Problems, 2011. [pdf]
- Dey, Fan, Wang: Computing topological persistence for simplicial maps. SoCG, 2014. [pdf]
- Dey, Shi, Wang: SimBa: An Efficient Tool for Approximating Rips-filtration
Persistence via Simplicial Batch-collapse. J. Exp. Algorithmics, 2019. [pdf]
- Curry, Ghrist, Nanda: Discrete Morse theory for computing cellular sheaf cohomology. FoCM, 2016. [pdf]
Topological inference
- Niyogi, Smale, Weinberger: Finding the Homology of Submanifolds with High Confidence from Random Samples. DCG, 2008. [pdf]
- Chazal, Oudot: Towards Persistence-Based Reconstruction in Euclidean Spaces. SoCG 2008. [pdf]
- Buchet et al.: Efficient and Robust Persistent Homology for Measures. CGTA, 2016. [pdf]
Topological data analysis
- Carrière, Chazal, Ike, Lacombe, Royer, Umeda: PersLay: A Simple and Versatile Neural Network Layer for Persistence Diagrams. Preprint, 2019. [pdf]
- 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]
- Carrière, Chazal, Glisse, Ike, Kannan: Optimizing persistent homology based functions. ICML, 2021. [pdf]
Your task is to read and understand the paper (even if not in full). In particular, you should focus on its goals, challenges, proposed methods, guarantees, experimental results, and limitations. 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 talk with slides and
be prepared for an ensuing discussion. No written report
is expected.
Last modification: Sept. 21 2023