Weronika Wrzos-Kaminska

I am a PhD student in Computer Science at EPFL, where I am advised by Michael Kapralov.

I am broadly interested in theoretical computer science. My research focuses on graph algorithms, including sublinear algorithms, clustering and spectral techniques.

Before joining EPFL, I completed my undergraduate and Master’s degree in Mathematics at the University of Cambridge.

Publications

  • Recovering Communities in Structured Random Graphs
    Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska
    ITCS 2026 [arXiv]
  • Spectral Clustering in Birthday Paradox Time
    Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska
    SODA 2026 [arXiv]
  • Spectral Clustering with Side Information
    Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova, Silvio Lattanzi, Davide Mazzali, Weronika Wrzos-Kaminska
    SODA 2026 [arXiv]
  • Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
    Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar, Weronika Wrzos-Kaminska
    ICALP 2025 [arXiv]
  • On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
    Aditya Bhaskara, Agastya Vibhuti Jha, Michael Kapralov, Naren Sarayu Manoj, Davide Mazzali, Weronika Wrzos-Kaminska
    NeurIPS 2024 [arXiv]
  • Weighted Matching in the Random-Order Streaming and Robust Communication Models
    Diba Hashemi, Weronika Wrzos-Kaminska (student authors only)
    APPROX 2024 (Invited to ToC special issue) [arXiv]

Teaching

  • Algorithms I, EPFL
  • Algorithms II, EPFL
  • Theory of Computation, EPFL