Ekaterina Kochetkova

ekaterina.kochetkova@epfl.ch

Academic Experience

I am a third year CS PhD student at EPFL working with Michael Kapralov. I am broadly interested in theoretical computer science. One direction of my current work is applying spectral graph theory to sublinear algorithm design. Another branch is optimization the memory/runtime of LLM inference, emphasizing algorithms with strong theoretical guarantees.

Publications

Spectral Clustering with Side Information

(alphabetical) Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova, Silvio Lattanzi, Davide Mazzali, Weronika Wrzos-Kaminska

In the ACM–SIAM Symposium on Discrete Algorithms (SODA), 2026

Spectral clustering in birthday paradox time

(alphabetical) Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska

In the ACM–SIAM Symposium on Discrete Algorithms (SODA), 2026

Streaming Attention Approximation via Discrepancy Theory

Ekaterina Kochetkova, Kshiteej Sheth, Insu Han, Amir Zandieh, Michael Kapralov

In Advances in Neural Information Processing Systems (NeurIPS), 2025 (Spotlight)

A KV‑cache compression method based on discrepancy theory, offering provable approximation guarantees and strong empirical performance on long‑context benchmarks

arXiv code

Pre-PhD Work

A new Andrews--Crandall-type identity and the number of integer solutions to \(x^2+2y^2+2z^2=n\)

(alphabetical) Mariia Dospolova, Ekaterina Kochetkova, Eric Todd Mortenson

In Ramanujan Journal 63 (2024), no. 4, 969-994

arXiv

Teaching

EPFL

CS-450 Advanced Algorithms

CS-251 Theory of Computation

Service

Conference review: SODA, ITCS.