Michael Kapralov

Michael Kapralov is an Associate Professor in the School of Computer and Communication Sciences at École Polytechnique Fédérale de Lausanne (EPFL), where he leads research at the Theory Group. His work spans multiple departments including the Laboratory of Theory of Computation 4 and the Doctoral Program in Computer Science and Communications. Kapralov's research focuses on theoretical computer science, particularly sublinear algorithms for big data analysis, with applications in streaming, sketching, sparse recovery, and Fourier sampling.

• University: EPFL
• School: School of Computer and Communication Sciences
• Department: Theory Group
• Academic Rank: Associate Professor

Education: Kapralov earned his Ph.D. in Computer Science from Stanford iCME under the supervision of Ashish Goel. He subsequently held postdoctoral positions at the Mit CSAIL Theory of Computation Group with Piotr Indyk and as a Herman Goldstine Postdoctoral Fellow at IBM T. J. Watson Research Center.

• Ph.D.: Stanford iCME (2012), advisor: Ashish Goel
• Postdoctoral: MIT CSAIL (2012-2014), IBM Watson (2014)

Research Interests: Kapralov's work addresses fundamental challenges in processing large-scale data through rigorous mathematical models. His contributions include advancements in sublinear algorithms, streaming complexity, spectral sparsification, sparse Fourier transforms, and differential privacy. He has developed techniques for dimension-independent signal processing, kernel ridge regression, and graph spanners, with theoretical guarantees and practical implications for machine learning and data analysis.

Scientific Awards: Kapralov received the ERC Starting Grant SUBLINEAR (2018-2023) and the Gene H. Golub Dissertation Award (2012).

Advising: He has supervised numerous Ph.D. students and postdoctoral researchers, including Ekaterina Kochetkova, Grzegorz Gluch, Kshiteej Sheth, and Amir Zandieh, many of whom have taken academic or industry positions at institutions like UC Berkeley, National University of Singapore, and Google Zurich.

Collaborations and Teaching: Kapralov co-organizes the Turing Course for high school students, leads the Reading Group on Foundations of Deep Learning, and contributes to academic initiatives such as Theory Coffee and the Swiss Winter School on Theoretical Computer Science. He teaches courses like Sublinear Algorithms for Big Data Analysis and Algorithms II, focusing on advanced algorithm design and analysis.