Filtered Backprojection Inversion of the Cone Beam Transform for a General Class of Curves. - Alexander Katsevich; Mikhail Kapralov (SIAM J. Appl. Math., 2007)

A Study of 1PI Algorithms for a General Class of Curves. - Mikhail Kapralov; Alexander Katsevich (SIAM J. Imaging Sci., 2008)

Factor Modeling for Advertisement Targeting. - Ye Chen; Michael Kapralov; Dmitry Pavlov; John F. Canny (NIPS, 2009)

Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs - Ashish Goel; Michael Kapralov; Sanjeev Khanna (CoRR, 2009)

Improved Bounds for Online Stochastic Matching. - Bahman Bahmani; Michael Kapralov (ESA (1), 2010)

Perfect matchings in o(n log n) time in regular bipartite graphs. - Ashish Goel; Michael Kapralov; Sanjeev Khanna (STOC, 2010)

Graph Sparsification via Refinement Sampling - Ashish Goel; Michael Kapralov; Sanjeev Khanna (CoRR, 2010)

Perfect matchings via uniform sampling in regular bipartite graphs. - Ashish Goel; Michael Kapralov; Sanjeev Khanna (ACM Trans. Algorithms, 2010)

Multiplicative Approximations of Random Walk Transition Probabilities. - Michael Kapralov; Rina Panigrahy (APPROX-RANDOM, 2011)

Prediction strategies without loss. - Michael Kapralov; Rina Panigrahy (NIPS, 2011)

Embedding Paths into Trees: VM Placement to Minimize Congestion. - Debojyoti Dutta; Michael Kapralov; Ian Post; Rajendra Shinde (ESA, 2012)

NNS Lower Bounds via Metric Expansion for l ∞ and EMD. - Michael Kapralov; Rina Panigrahy (ICALP (1), 2012)

Spectral sparsification via random spanners. - Michael Kapralov; Rina Panigrahy (ITCS, 2012)

On the communication and streaming complexity of maximum bipartite matching. - Ashish Goel; Michael Kapralov; Sanjeev Khanna (SODA, 2012)

Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service - Debojyoti Dutta; Michael Kapralov; Ian Post; Rajendra Shinde (CoRR, 2012)

Single pass sparsification in the streaming model with edge deletions - Ashish Goel; Michael Kapralov; Ian Post (CoRR, 2012)

Online and stochastic variants of welfare maximization - Mikhail Kapralov; Ian Post; Jan Vondrák (CoRR, 2012)

Improved lower bounds for matchings in the streaming model - Michael Kapralov (CoRR, 2012)

Better bounds for matchings in the streaming model. - Michael Kapralov (SODA, 2013)

Online Submodular Welfare Maximization: Greedy is Optimal. - Michael Kapralov; Ian Post; Jan Vondrák (SODA, 2013)

On differentially private low rank approximation. - Michael Kapralov; Kunal Talwar (SODA, 2013)

Perfect Matchings in O(nlog n) Time in Regular Bipartite Graphs. - Ashish Goel; Michael Kapralov; Sanjeev Khanna (SIAM J. Comput., 2013)

Sample-Optimal Fourier Sampling in Any Constant Dimension. - Piotr Indyk; Michael Kapralov (FOCS, 2014)

Spanners and sparsifiers in dynamic streams. - Michael Kapralov; David P. Woodruff (PODC, 2014)

(Nearly) Sample-Optimal Sparse Fourier Transform. - Piotr Indyk; Michael Kapralov; Eric Price 001 (SODA, 2014)

Approximating matching size from random streams. - Michael Kapralov; Sanjeev Khanna; Madhu Sudan 001 (SODA, 2014)

Sample-Optimal Fourier Sampling in Any Constant Dimension - Part I. - Piotr Indyk; Michael Kapralov (CoRR, 2014)

Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search. - Michael Kapralov (PODS, 2015)

Streaming Lower Bounds for Approximating MAX-CUT. - Michael Kapralov; Sanjeev Khanna; Madhu Sudan 001 (SODA, 2015)

How to Fake Multiply by a Gaussian Matrix. - Michael Kapralov; Vamsi K. Potluru; David P. Woodruff (ICML, 2016)

Subgraph Counting: Color Coding Beyond Trees. - Venkatesan T. Chakaravarthy; Michael Kapralov; Prakash Murali; Fabrizio Petrini; Xinyu Que; Yogish Sabharwal; Baruch Schieber (IPDPS, 2016)

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. - Michael Kapralov (STOC, 2016)

Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average. - Michael Kapralov (FOCS, 2017)

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 (FOCS, 2017)

Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees. - Haim Avron; Michael Kapralov; Cameron Musco; Christopher Musco; Ameya Velingker; Amir Zandieh (ICML, 2017)

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. - Michael Kapralov; Sanjeev Khanna; Madhu Sudan 001; Ameya Velingker (SODA, 2017)

An adaptive sublinear-time block sparse fourier transform. - Volkan Cevher; Michael Kapralov; Jonathan Scarlett; Amir Zandieh (STOC, 2017)

Single Pass Spectral Sparsification in Dynamic Streams. - Michael Kapralov; Yin Tat Lee; Cameron Musco; Christopher Musco; Aaron Sidford (SIAM J. Comput., 2017)

Testing Graph Clusterability: Algorithms and Lower Bounds. - Ashish Chiplunkar; Michael Kapralov; Sanjeev Khanna; Aida Mousavifar; Yuval Peres (FOCS, 2018)

The Sketching Complexity of Graph and Hypergraph Counting. - John Kallaugher; Michael Kapralov; Eric Price 001 (FOCS, 2018)

Online Matching with General Arrivals. - Buddhima Gamlath; Michael Kapralov; Andreas Maggiori; Ola Svensson; David Wajc (FOCS, 2019)

A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. - Sepehr Assadi; Michael Kapralov; Sanjeev Khanna (ITCS, 2019)

Efficiently Learning Fourier Sparse Set Functions. - Andisheh Amrollahi; Amir Zandieh; Michael Kapralov; Andreas Krause 001 (NeurIPS, 2019)

Dimension-independent Sparse Fourier Transform. - Michael Kapralov; Ameya Velingker; Amir Zandieh (SODA, 2019)

A universal sampling method for reconstructing signals with simple Fourier transforms. - Haim Avron; Michael Kapralov; Cameron Musco; Christopher Musco; Ameya Velingker; Amir Zandieh (STOC, 2019)

An optimal space lower bound for approximating MAX-CUT. - Michael Kapralov; Dmitry Krachun (STOC, 2019)

Perfect Matchings in Õ (n 1.5) Time in Regular Bipartite Graphs. - Ashish Goel; Michael Kapralov; Sanjeev Khanna (Comb., 2019)

Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space. - Michael Kapralov; Navid Nouri; Aaron Sidford; Jakab Tardos (CoRR, 2019)

Faster Spectral Sparsification in Dynamic Streams. - Michael Kapralov; Aida Mousavifar; Cameron Musco; Christopher Musco; Navid Nouri (CoRR, 2019)

Practice of Streaming and Dynamic Graphs: Concepts, Models, Systems, and Parallelism. - Maciej Besta; Marc Fischer; Vasiliki Kalavri; Michael Kapralov; Torsten Hoefler (CoRR, 2019)

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing. - Amir Zandieh; Navid Nouri; Ameya Velingker; Michael Kapralov; Ilya P. Razenshteyn (AISTATS, 2020)

Kernel Density Estimation through Density Constrained Near Neighbor Search. - Moses Charikar; Michael Kapralov; Navid Nouri; Paris Siminelakis (FOCS, 2020)

Oblivious Sketching of High-Degree Polynomial Kernels. - Thomas D. Ahle; Michael Kapralov; Jakob Bæk Tejs Knudsen; Rasmus Pagh; Ameya Velingker; David P. Woodruff; Amir Zandieh (SODA, 2020)

Differentially Private Release of Synthetic Graphs. - Marek Eliás 001; Michael Kapralov; Janardhan Kulkarni; Yin Tat Lee (SODA, 2020)

Fast and Space Efficient Spectral Sparsification in Dynamic Streams. - Michael Kapralov; Aida Mousavifar; Cameron Musco; Christopher Musco; Navid Nouri; Aaron Sidford; Jakab Tardos (SODA, 2020)

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples. - Michael Kapralov; Slobodan Mitrovic; Ashkan Norouzi-Fard; Jakab Tardos (SODA, 2020)

Spectral Hypergraph Sparsifiers of Nearly Linear Size. - Michael Kapralov; Robert Krauthgamer; Jakab Tardos; Yuichi Yoshida (FOCS, 2021)

Efficient and Local Parallel Random Walks. - Michael Kapralov; Silvio Lattanzi; Navid Nouri; Jakab Tardos (NeurIPS, 2021)

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model. - Arnold Filtser; Michael Kapralov; Navid Nouri (SODA, 2021)

Spectral Clustering Oracles in Sublinear Time. - Grzegorz Gluch; Michael Kapralov; Silvio Lattanzi; Aida Mousavifar; Christian Sohler (SODA, 2021)

Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model. - Michael Kapralov (SODA, 2021)

Communication Efficient Coresets for Maximum Matching. - Michael Kapralov; Gilbert Maystre; Jakab Tardos (SOSA, 2021)

Towards tight bounds for spectral sparsification of hypergraphs. - Michael Kapralov; Robert Krauthgamer; Jakab Tardos; Yuichi Yoshida (STOC, 2021)

Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs. - Karl Bringmann; Michael Kapralov; Mikhail Makarov; Vasileios Nakos; Amir Yagudin; Amir Zandieh (CoRR, 2021)

Approximating Local Graph Structure in Almost Random Order Streams. - Ashish Chiplunkar; John Kallaugher; Michael Kapralov; Eric Price 001 (CoRR, 2021)

Factorial Lower Bounds for (Almost) Random Order Streams. - Ashish Chiplunkar; John Kallaugher; Michael Kapralov; Eric Price 001 (FOCS, 2022)

Motif Cut Sparsifiers. - Michael Kapralov; Mikhail Makarov; Sandeep Silwal; Christian Sohler; Jakab Tardos (FOCS, 2022)

Noisy Boolean Hidden Matching with Applications. - Michael Kapralov; Amulya Musipatla; Jakab Tardos; David P. Woodruff; Samson Zhou (ITCS, 2022)

Simulating Random Walks in Random Streams. - John Kallaugher; Michael Kapralov; Eric Price 001 (SODA, 2022)

Learning Hierarchical Structure of Clusterable Graphs. - Michael Kapralov; Akash Kumar 009; Silvio Lattanzi; Aida Mousavifar (CoRR, 2022)

On Constructing Spanners from Random Gaussian Projections. - Sepehr Assadi; Michael Kapralov; Huacheng Yu (APPROX/RANDOM, 2023)

Expander Decomposition in Dynamic Streams. - Arnold Filtser; Michael Kapralov; Mikhail Makarov (ITCS, 2023)

Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms. - Karl Bringmann; Michael Kapralov; Mikhail Makarov; Vasileios Nakos; Amir Yagudin; Amir Zandieh (SODA, 2023)

Learning Hierarchical Cluster Structure of Graphs in Sublinear Time. - Michael Kapralov; Akash Kumar 009; Silvio Lattanzi; Aida Mousavifar (SODA, 2023)

Toeplitz Low-Rank Approximation with Sublinear Query Complexity. - Michael Kapralov; Hannah Lawrence; Mikhail Makarov; Cameron Musco; Kshiteej Sheth (SODA, 2023)

Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems. - Maciej Besta; Marc Fischer; Vasiliki Kalavri; Michael Kapralov; Torsten Hoefler (IEEE Trans. Parallel Distributed Syst., 2023)

Streaming Algorithms for Connectivity Augmentation. - Ce Jin 001; Michael Kapralov; Sepideh Mahabadi; Ali Vakilian (ICALP, 2024)

On the Streaming Complexity of Expander Decomposition. - Yu Chen 039; Michael Kapralov; Mikhail Makarov; Davide Mazzali (ICALP, 2024)

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models. - Aditya Bhaskara; Agastya Vibhuti Jha; Michael Kapralov; Naren Manoj; Davide Mazzali; Weronika Wrzos-Kaminska (NeurIPS, 2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. - Moses Charikar; Michael Kapralov; Erik Waingarten (SODA, 2024)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds. - Michael Kapralov; Akash Kumar 009; Silvio Lattanzi; Aida Mousavifar; Weronika Wrzos-Kaminska (ICALP, 2025)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions. - Piotr Indyk; Michael Kapralov; Kshiteej Sheth; Tal Wagner (ICLR, 2025)

BalanceKV: KV Cache Compression through Discrepancy Theory. - Insu Han; Michael Kapralov; Ekaterina Kochetkova; Kshiteej Sheth; Amir Zandieh (CoRR, 2025)

On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space. - Michael Kapralov; Mikhail Makarov; Christian Sohler (Proc. ACM Manag. Data, 2025)