| 2026 | SODA | Spectral Clustering with Side Information. | Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova, Silvio Lattanzi, Davide Mazzali, Weronika Wrzos-Kaminska |
| 2026 | SODA | Spectral clustering in birthday paradox time. | Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska |
| 2026 | SODA | Sublinear Time Low-Rank Approximation of Hankel Matrices. | Michael Kapralov, Cameron Musco, Kshiteej Sheth |
| 2025 | FOCS | Generalized Flow in Nearly-linear Time on Moderately Dense Graphs. | Shunhua Jiang, Michael Kapralov, Lawrence Li, Aaron Sidford |
| 2025 | ICALP | Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds. | Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar, Weronika Wrzos-Kaminska |
| 2025 | ICLR | Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions. | Piotr Indyk, Michael Kapralov, Kshiteej Sheth, Tal Wagner |
| 2024 | ICALP | Streaming Algorithms for Connectivity Augmentation. | Ce Jin, Michael Kapralov, Sepideh Mahabadi, Ali Vakilian |
| 2024 | ICALP | On the Streaming Complexity of Expander Decomposition. | Yu Chen, Michael Kapralov, Mikhail Makarov, Davide Mazzali |
| 2024 | SODA | A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. | Moses Charikar, Michael Kapralov, Erik Waingarten |
| 2023 | SODA | Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms. | Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh |
| 2023 | SODA | Learning Hierarchical Cluster Structure of Graphs in Sublinear Time. | Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar |
| 2023 | SODA | Toeplitz Low-Rank Approximation with Sublinear Query Complexity. | Michael Kapralov, Hannah Lawrence, Mikhail Makarov, Cameron Musco, Kshiteej Sheth |
| 2022 | FOCS | Factorial Lower Bounds for (Almost) Random Order Streams. | Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price |
| 2022 | FOCS | Motif Cut Sparsifiers. | Michael Kapralov, Mikhail Makarov, Sandeep Silwal, Christian Sohler, Jakab Tardos |
| 2022 | SODA | Simulating Random Walks in Random Streams. | John Kallaugher, Michael Kapralov, Eric Price |
| 2021 | FOCS | Spectral Hypergraph Sparsifiers of Nearly Linear Size. | Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
| 2021 | SODA | Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model. | Arnold Filtser, Michael Kapralov, Navid Nouri |
| 2021 | SODA | Spectral Clustering Oracles in Sublinear Time. | Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler |
| 2021 | SODA | Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model. | Michael Kapralov |
| 2021 | STOC | Towards tight bounds for spectral sparsification of hypergraphs. | Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
| 2020 | AISTATS | Scaling up Kernel Ridge Regression via Locality Sensitive Hashing. | Amir Zandieh, Navid Nouri, Ameya Velingker, Michael Kapralov, Ilya P. Razenshteyn |
| 2020 | FOCS | Kernel Density Estimation through Density Constrained Near Neighbor Search. | Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis |
| 2020 | SODA | Oblivious Sketching of High-Degree Polynomial Kernels. | Thomas D. Ahle, Michael Kapralov, Jakob Bk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh |
| 2020 | SODA | Differentially Private Release of Synthetic Graphs. | Marek Elis, Michael Kapralov, Janardhan Kulkarni, Yin Tat Lee |
| 2020 | SODA | Fast and Space Efficient Spectral Sparsification in Dynamic Streams. | Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos |
| 2020 | SODA | Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples. | Michael Kapralov, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakab Tardos |
| 2019 | FOCS | Online Matching with General Arrivals. | Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc |
| 2019 | SODA | Dimension-independent Sparse Fourier Transform. | Michael Kapralov, Ameya Velingker, Amir Zandieh |
| 2019 | STOC | A universal sampling method for reconstructing signals with simple Fourier transforms. | Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh |
| 2019 | STOC | An optimal space lower bound for approximating MAX-CUT. | Michael Kapralov, Dmitry Krachun |
| 2018 | FOCS | Testing Graph Clusterability: Algorithms and Lower Bounds. | Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres |
| 2018 | FOCS | The Sketching Complexity of Graph and Hypergraph Counting. | John Kallaugher, Michael Kapralov, Eric Price |
| 2017 | FOCS | Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average. | Michael Kapralov |
| 2017 | FOCS | Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. | Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh |
| 2017 | ICML | Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees. | Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh |
| 2017 | SODA | (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. | Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker |
| 2017 | STOC | An adaptive sublinear-time block sparse fourier transform. | Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh |
| 2016 | ICML | How to Fake Multiply by a Gaussian Matrix. | Michael Kapralov, Vamsi K. Potluru, David P. Woodruff |
| 2016 | STOC | Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. | Michael Kapralov |
| 2015 | PODS | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search. | Michael Kapralov |
| 2015 | SODA | Streaming Lower Bounds for Approximating MAX-CUT. | Michael Kapralov, Sanjeev Khanna, Madhu Sudan |
| 2014 | FOCS | Sample-Optimal Fourier Sampling in Any Constant Dimension. | Piotr Indyk, Michael Kapralov |
| 2014 | FOCS | Single Pass Spectral Sparsification in Dynamic Streams. | Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford |
| 2014 | PODC | Spanners and sparsifiers in dynamic streams. | Michael Kapralov, David P. Woodruff |
| 2014 | SODA | (Nearly) Sample-Optimal Sparse Fourier Transform. | Piotr Indyk, Michael Kapralov, Eric Price |
| 2014 | SODA | Approximating matching size from random streams. | Michael Kapralov, Sanjeev Khanna, Madhu Sudan |
| 2013 | SODA | Better bounds for matchings in the streaming model. | Michael Kapralov |
| 2013 | SODA | Online Submodular Welfare Maximization: Greedy is Optimal. | Michael Kapralov, Ian Post, Jan Vondrk |
| 2013 | SODA | On differentially private low rank approximation. | Michael Kapralov, Kunal Talwar |
| 2012 | ESA | Embedding Paths into Trees: VM Placement to Minimize Congestion. | Debojyoti Dutta, Michael Kapralov, Ian Post, Rajendra Shinde |
| 2012 | ICALP | NNS Lower Bounds via Metric Expansion for l ∞ and EMD. | Michael Kapralov, Rina Panigrahy |
| 2012 | SODA | On the communication and streaming complexity of maximum bipartite matching. | Ashish Goel, Michael Kapralov, Sanjeev Khanna |
| 2010 | ESA | Improved Bounds for Online Stochastic Matching. | Bahman Bahmani, Michael Kapralov |
| 2010 | STOC | Perfect matchings in o( | Ashish Goel, Michael Kapralov, Sanjeev Khanna |
| 2009 | SODA | Perfect matchings via uniform sampling in regular bipartite graphs. | Ashish Goel, Michael Kapralov, Sanjeev Khanna |