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 Planted Colorings in Sublinear Time
    Weronika Wrzos-Kaminska
    To appear in RANDOM 2026
  • 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 paper)
    APPROX 2024 (Invited to ToC special issue) [arXiv]

Teaching

  • Algorithms I
    Teaching Assistant · Fall 2022, Spring 2024 · EPFL
  • Algorithms II
    Teaching Assistant · Spring 2023, Fall 2023, 2024, 2025 · EPFL
  • Theory of Computation
    Teaching Assistant · Spring 2022 · EPFL

Service

Conference review: STOC, FOCS, ITCS, ICALP, ESA, RANDOM