Chris Schwiegelshohn   Associate Professor Department of Computer Science Aarhus University

Velkommen, Benvenuto, Welcome!

In case you are confusing me with some other Chris Schwiegelshohn out there, I am the one working as a faculty member of the computer science department of Aarhus University.

I was previously working at Sapienza University. If you are a student with questions about one of my past courses, please contact me under <cschwiegelshohn"at"gmail.com>.

If you are not a former student of mine but want to contact me anyway, well it's the same email.

I work mostly on algorithm design. In particular, I like online, streaming, approximation and learning algorithms.

The most up to date list of publications is available at dblp or google scholar. If you cannot access them and would like to read them, email me.

Publications:

• A (2 + ε)-Approximation Algorithm for Metric k-Median, STOC 2025. With Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Ola Svensson.

• A Tight VC-Dimension Analysis of Clustering Coresets with Applications, SODA 2025. With Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, and David Saulpic.

• Fair Projections as a Means Towards Balanced Recommendations, ACM Trans. Intell. Syst. Technol. 2025. With Aris Anagnostopoulos, Luca Becchetti, Matteo Bohm, Adriano Fazzone, Stefano Leonardi, and Cristina Menghini.

• Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds, FOCS 2024. With Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu and David Saulpic.

• Optimal Coresets for Low-Dimensional Geometric Median, ICML 2024. With Peyman Afshani.

• Sparse Dimensionality Reduction Revisted, ICML 2024. With Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, and Jelani Nelson.

• Low-distortion clustering with ordinal and limited cardinal information, AAAI 2024. With Jakob Burkhardt, Ioannis Caragiannis, Karl Fehrs, Matteo Russo, and Sudarshan Shyam.

• Settling Time vs. Accuracy Tradeoffs for Clustering Big Data, SIGMOD 2024. With Andrew Draganov and David Saulpic.

• Adaptive Out-Orientations with Applications, SODA 2024. With Chandra Chekuri, Aleksander Bjørn Grodt Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, and Eva Rotenberg.

• On Generalization Bounds for Projective Clustering, NeurIPS 2023. With Maria Sofia Bucarelli, Matilde Fjeldsø Larsen, and Mads Bech Toftrup.

• Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation, FOCS 2023. With Vincent Cohen-Addad and David Saulpic.

• Optimal Sketching Bounds for Sparse Linear Regression, AISTATS 2023. With Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, and David Woodruff.

• Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median, SODA 2023. With Vincent Cohen-Addad, Euiwoong Lee, and Fabrizio Grandoni.

• Improved Coresets for Euclidean k-Means, NeurIPS 2022. With Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Omar Ali Sheikh-Omar.

• The Power of Uniform Sampling for Coresets, FOCS 2022. With Vladmir Braverman, Vincent Cohen-Addad, Shaofeng Jiang, Robert Krauthgamer, Mads Bech Toftrup, and Xuan Wu.

• An Empirical Evaluation of k-Means Coresets, ESA 2022 - Best Paper Award. With Omar Ali Sheikh-Omar. pdf

• Scalable Differentially Private Clustering via Hierarchically Separated Trees, KDD 2022. With Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Andres Munoz Medina, Vahab Mirrokni, David Saulpic, and Sergei Vassilvitskii. pdf

• Towards Optimal Lower Bounds for k-median and k-means Coresets, STOC 2022. With Vincent Cohen-Addad, Kasper Green Larsen, and David Saulpic. pdf

• Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds, SOSA 2022. With Fabrizio Grandoni, Shay Solomon, and Amitai Uzrad. pdf

• Polynomial Time Approximation Schemes for All 1-Center Problems on Metric Rational Set Similarities, Algorithmica 2021. With Marc Bury, Michele Gentili, and Mara Sorella. pdf

• Algorithms for fair k-clustering with multiple protected attributes, Oper. Res. Lett. 2021. With Matteo Bohm, Adriano Fazzone, Stefano Leonardi, and Cristina Menghini. pdf

• Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces, NeurIPS 2021 - Spotlight Presentation. With Vincent Cohen-Addad and David Saulpic. pdf

• A New Coreset Framework for Clustering, STOC 2021. With Vincent Cohen-Addad and David Saulpic. pdf

• Similarity Search for Dynamic Data Streams, IEEE Trans. Knowl. Data Eng. 2020. With Marc Bury and Mara Sorella. pdf

• Spectral Relaxations and Fair Densest Subgraph, CIKM 2020. With Aris Anagnostopoulos, Luca Becchetti, Adriano Fazzone, and Cristina Menghini. pdf

• Commitment and Slack for Online Load Maximization , SPAA 2020. With Samin Jamalabadi and Uwe Schwiegelshohn. pdf

• Structural Results on Matching Estimation with Applications to Streaming, Algorithmica 2019. With Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova, and Samson Zhou. pdf

• Fully Dynamic Consistent Facility Location, NeurIPS 2019. With Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, and David Saulpic. pdf

• Fair Coresets and Streaming Algorithms for Fair k-Means, WAOA 2019. With Melanie Schmidt and Christian Sohler. pdf

• Oblivious Dimension Reduction for k-Means -- Beyond Subspaces and the Johnson-Lindenstrauss Lemma, STOC 2019. With Luca Becchetti, Marc Bury, Vincent Cohen-Addad, and Fabrizio Grandoni. pdf
  I encourage anyone interested in this work to read the paper by Makarychev, Makarychev, and Razenshteyn. Independently from us, they obtained essentially optimal bounds for the same problem.

• (1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time, SODA 2019. With Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, and Shay Solomon. pdf

• Coresets-Methods and History: A Theoreticians Design Pattern for Approximation and Streaming Algorithms, Künstliche Intelligenz 2018. With Alexander Munteanu. pdf

• On Coresets for Logistic Regression, NeurIPS 2018 - Spotlight Presentation. With Alexander Munteanu, Christian Sohler, and David Woodruff. pdf

• Sketch 'Em All: Fast Approximate Similarity Search in Dynamic Data Streams, WSDM 2018. With Marc Bury and Mara Sorella.

• On the Local Structure of Stable Clustering Instances, FOCS 2017. With Vincent Cohen-Addad. pdf

• On Finding the Jaccard Center, ICALP 2017. With Marc Bury. pdf

• The Power of Migration for Online Slack Scheduling, ESA 2016. With Uwe Schwiegelshohn. pdf

• Diameter and k-Center in Sliding Windows, ICALP 2016. With Vincent Cohen-Addad and Christian Sohler. pdf

• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams, ESA 2015. With Marc Bury.

• BICO: BIRCH Meets Coresets for k-Means Clustering, ESA 2013. With Hendrik Fichtenberger, Marc Gillé (now Bury), Melanie Schmidt, and Christian Sohler. pdf

• Solving the Minimum String Cover Problem, ALENEX 2012. With Stefan Canzar, Tobias Marshall, and Sven Rahmann. pdf