I am a third year CS PhD student at EPFL working with Prof. Michael Kapralov. My current research is about sublinear graph algorithms and variations of Sparse Fourier Transform.

Before joining EPFL I got my bachelor's degree at MIPT.

You can reach me at mikhail.makarov at epfl dot ch.

Also see my Google Scholar and EPFL profiles.

SFT implementation

You can find the implementation of the algorithm from our SFT paper here.

Publications

Expander Decomposition in Dynamic Streams
A. Filtser, M. Kapralov and M. Makarov
ITCS 2023.

Toeplitz Low-Rank Approximation with Sublinear Query Complexity
M. Kapralov, H. Lawrence, M. Makarov, C. Musco and K. Sheth
SODA 2023.

Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs
K. Bringmann, M. Kapralov, M. Makarov, V. Nakos, A. Yagudin and A. Zandieh
SODA 2023.

Motif Cut Sparsifiers
M. Kapralov, M. Makarov, S. Silwal, C. Sohler and J. Tardos
FOCS 2022.