Michael Kapralov

I am an Associate Professor in the School of Computer and Communication Sciences at EPFL, and part of the Theory Group at EPFL.

Email: michael dot kapralov at epfl dot ch
Phone: +41 21 69 38143
Address: EPFL IC
Building INJ (INJ113)
Station 14
CH-1015 Lausanne

Interested in working with me? Apply to our PhD program and mention my name on your application. For an undergraduate summer internship, apply to the Summer@EPFL program.

Multiple postdoctoral positions available in the Theory Group: apply here.

Research: I am broadly interested in theoretical computer science, with an emphasis on theoretical foundations of big data analysis. Most of my algorithmic work is in sublinear algorithms, where specific directions include streaming, sketching, sparse recovery and Fourier sampling.

Bio: I completed my PhD at Stanford iCME, where I was advised by Ashish Goel. After graduating from Stanford I 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.

I am grateful to the European Research Council for their generous support (ERC Starting Grant SUBLINEAR, 2018-2023).

We are organizing the Turing Course, which introduces high school students to some of the gems of computer science. Also see our summer school on games and artificial intelligence, taught by the amazing Romain Edelmann.

Reading group on the Foundations of Deep Learning

Theory Coffee

EPFL Theory Seminar

We are organizing a Workshop on Learning: Optimization and Stochastics at EPFL between June 29th and July 1st 2022.

Swiss Winter School on Theoretical Computer Science (application deadline: November 1st).

Turing Course introducing high school students to the gems of computer science (registration deadline: 30th June 2023).

Teaching: Program Commitees: SOSA 2023, STOC 2022, RANDOM 2021, ICALP 2021, CSR 2021, SOSA 2021, ESA 2020, HALG 2020, SODA 2020, PODS 2019, FSTTCS 2018, ICALP 2017, FOCS 2015

Recent papers:
Pre-PhD work on imaging: