Christian Janos Lebeda

I am a postdoc in the Algorithms Group at the IT University of Copenhagen. I am also affiliated with the Basic Algorithms Research Copenhagen center and the Providentia Project. During my PhD I was advised by Rasmus Pagh and Martin Aumüller. My main research interest is the design and analysis of differentially private algorithms and data structures.


PLAN: Variance-Aware Differentially Private Mean Estimation
Martin Aumüller, Christian Janos Lebeda, Boel Nelson, and Rasmus Pagh.
To appear in Proceedings of Privacy Enhancing Technologies Symposium (PETS 2024)

Correlated-Output Differential Privacy and Applications to Dark Pools
James Hsin-yu Chiang, Bernardo David, Mariana Gama, and Christian Janos Lebeda.
Published in Advances in Financial Technologies (AFT 2023).

Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch
Christian Janos Lebeda and Jakub Tětek.
Published as distinguished paper in Principles of Database Systems symposium series (PODS 2023). Selected for 2023 ACM SIGMOD Research Highlight Awards.

Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access
Martin Aumüller, Christian Janos Lebeda, and Rasmus Pagh.
Published in Proceedings of Conference on Computer and Communications Security (CCS 2021). Poster accepted at Theory and Practice of Differential Privacy (TPDP 2021). Full version published in the Journal of Privacy and Confidentiality. I was accepted to the OpenDP Fellows Program 2021 during which I implemented our algorithm. Short version of paper available here.


  • Fall 2023 - Foundations of Probability
  • Spring 2021 & 2022 - Algorithmic Problem Solving