Michael Kapralov

I am an Assistant 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).

Theory Coffee

EPFL Theory Seminar

We are organizing a Workshop on Learning: Optimization and Stochastics at EPFL on 5-7th July 2020.

Swiss Winter School on Theoretical Computer Science (application deadline: November 15th).

Teaching: Program Commitees: 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: