Traversing the fft computation tree for dimension-independent sparse fourier transforms K Bringmann, M Kapralov, M Makarov, V Nakos, A Yagudin, A Zandieh Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2023 | 3* | 2023 |
Toeplitz low-rank approximation with sublinear query complexity M Kapralov, H Lawrence, M Makarov, C Musco, K Sheth Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2023 | 3 | 2023 |
Expander decomposition in dynamic streams A Filtser, M Kapralov, M Makarov arXiv preprint arXiv:2211.11384, 2022 | 3 | 2022 |
Logical complexity of induced subgraph isomorphism for certain families of graphs ME Zhukovskii, ED Kudryavtsev, MV Makarov, AS Shlychkova Sbornik: Mathematics 212 (4), 517, 2021 | 1* | 2021 |
On the Streaming Complexity of Expander Decomposition Y Chen, M Kapralov, M Makarov, D Mazzali arXiv preprint arXiv:2404.16701, 2024 | | 2024 |
On the adversarial robustness of Locality-Sensitive Hashing in Hamming space M Kapralov, M Makarov, C Sohler arXiv preprint arXiv:2402.09707, 2024 | | 2024 |
Motif Cut Sparsifiers M Kapralov, M Makarov, S Silwal, C Sohler, J Tardos 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS …, 2022 | | 2022 |
First-order definitions of subgraph isomorphism through the adjacency and order relations O Grigoryan, M Makarov, M Zhukovskii Moscow Journal of Combinatorics and Number Theory 9 (3), 293-302, 2020 | | 2020 |