Tenure Track Assistant Professor
Department of Computer Science
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.
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
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