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.

Publications you cannot find below you may be able to find at dblp or google scholar.

Publications:

• 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. 2024. 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