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 is part of the Theory Group. His research focuses on theoretical computer science with emphasis on the theoretical foundations of big data analysis.

Dr. Kapralov completed his PhD at Stanford iCME under the supervision of Ashish Goel. Following his doctoral studies, he spent two years as a postdoc at the Theory of Computation Group at MIT CSAIL working with Piotr Indyk, and then a year at the IBM T. J. Watson Research Center as a Herman Goldstine Postdoctoral Fellow.

His research primarily centers on sublinear algorithms, with specific directions including streaming algorithms, sketching techniques, sparse recovery, and Fourier sampling. Kapralov's work addresses fundamental questions in the theoretical computer science of big data, developing algorithms that can process massive datasets efficiently with limited computational resources. His approach often combines deep theoretical insights with practical considerations for real-world applications of theoretical computer science principles.

Analysis of Kapralov's recent publications reveals a strong focus on advancing the state of the art in sublinear-time algorithms, particularly for graph problems and kernel methods. His work demonstrates a consistent trajectory toward developing more efficient algorithms for fundamental computational problems while establishing tight theoretical bounds on what's possible in streaming and sublinear settings. There's a notable emphasis on bridging theoretical computer science with practical machine learning applications, particularly through kernel methods and Fourier analysis techniques.

• ERC Starting Grant SUBLINEAR (2018-2023)
• Gene H. Golub Dissertation Award
• Best paper award in CT at Fully3D 2007
• Institute of Physics (IoP) Select article

Professor Kapralov has advised numerous PhD students and postdocs who have gone on to successful careers in both academia and industry, including several who now hold faculty positions at prestigious institutions worldwide. He has also received significant research funding, most notably the European Research Council Starting Grant that supported his SUBLINEAR project from 2018 to 2023.

Within the EPFL academic community, Kapralov is actively involved in several initiatives including organizing the Turing Course for high school students, leading a reading group on the Foundations of Deep Learning, and participating in the EPFL Theory Seminar series. He also contributes to the broader theoretical computer science community through program committee service for major conferences including SOSA 2023 and STOC 2022.