Michael Kapralov

According to our database, Michael Kapralov authored at least 81 papers between 2007 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space.

Michael Kapralov, Mikhail Makarov, Christian Sohler

CoRR, 2024

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations.

Moses Charikar, Michael Kapralov, Erik Waingarten

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

On the Streaming Complexity of Expander Decomposition.

Yu Chen, Michael Kapralov, Mikhail Makarov, Davide Mazzali

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Streaming Algorithms for Connectivity Augmentation.

Ce Jin, Michael Kapralov, Sepideh Mahabadi, Ali Vakilian

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

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., June, 2023

Toeplitz Low-Rank Approximation with Sublinear Query Complexity.

Michael Kapralov, Hannah Lawrence, Mikhail Makarov, Cameron Musco, Kshiteej Sheth

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Learning Hierarchical Cluster Structure of Graphs in Sublinear Time.

Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms.

Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Expander Decomposition in Dynamic Streams.

Arnold Filtser, Michael Kapralov, Mikhail Makarov

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

On Constructing Spanners from Random Gaussian Projections.

Sepehr Assadi, Michael Kapralov, Huacheng Yu

Proceedings of the Approximation, 2023

2022

Learning Hierarchical Structure of Clusterable Graphs.

Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar

CoRR, 2022

Simulating Random Walks in Random Streams.

John Kallaugher, Michael Kapralov, Eric Price

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Noisy Boolean Hidden Matching with Applications.

Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Motif Cut Sparsifiers.

Michael Kapralov, Mikhail Makarov, Sandeep Silwal, Christian Sohler, Jakab Tardos

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Factorial Lower Bounds for (Almost) Random Order Streams.

Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Approximating Local Graph Structure in Almost Random Order Streams.

Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price

CoRR, 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

Towards tight bounds for spectral sparsification of hypergraphs.

Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Communication Efficient Coresets for Maximum Matching.

Michael Kapralov, Gilbert Maystre, Jakab Tardos

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model.

Michael Kapralov

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Spectral Clustering Oracles in Sublinear Time.

Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model.

Arnold Filtser, Michael Kapralov, Navid Nouri

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Efficient and Local Parallel Random Walks.

Michael Kapralov, Silvio Lattanzi, Navid Nouri, Jakab Tardos

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Spectral Hypergraph Sparsifiers of Nearly Linear Size.

Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples.

Michael Kapralov, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakab Tardos

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams.

Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Differentially Private Release of Synthetic Graphs.

Marek Eliás, Michael Kapralov, Janardhan Kulkarni, Yin Tat Lee

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 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

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Kernel Density Estimation through Density Constrained Near Neighbor Search.

Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing.

Amir Zandieh, Navid Nouri, Ameya Velingker, Michael Kapralov, Ilya P. Razenshteyn

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Practice of Streaming and Dynamic Graphs: Concepts, Models, Systems, and Parallelism.

Maciej Besta, Marc Fischer, Vasiliki Kalavri, Michael Kapralov, Torsten Hoefler

CoRR, 2019

Oblivious Sketching of High-Degree Polynomial Kernels.

Michael Kapralov, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh

CoRR, 2019

Faster Spectral Sparsification in Dynamic Streams.

Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri

CoRR, 2019

Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space.

Michael Kapralov, Navid Nouri, Aaron Sidford, Jakab Tardos

CoRR, 2019

Perfect Matchings in Õ (n 1.5) Time in Regular Bipartite Graphs.

Ashish Goel, Michael Kapralov, Sanjeev Khanna

Comb., 2019

An optimal space lower bound for approximating MAX-CUT.

Michael Kapralov, Dmitry Krachun

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

A universal sampling method for reconstructing signals with simple Fourier transforms.

Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Dimension-independent Sparse Fourier Transform.

Michael Kapralov, Ameya Velingker, Amir Zandieh

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Efficiently Learning Fourier Sparse Set Functions.

Andisheh Amrollahi, Amir Zandieh, Michael Kapralov, Andreas Krause

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling.

Sepehr Assadi, Michael Kapralov, Sanjeev Khanna

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Online Matching with General Arrivals.

Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

The Sketching Complexity of Graph and Hypergraph Counting.

John Kallaugher, Michael Kapralov, Eric Price

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Testing Graph Clusterability: Algorithms and Lower Bounds.

Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Single Pass Spectral Sparsification in Dynamic Streams.

Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford

SIAM J. Comput., 2017

An adaptive sublinear-time block sparse fourier transform.

Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space.

Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Proceedings of the 34th International Conference on Machine Learning, 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

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average.

Michael Kapralov

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time.

Michael Kapralov

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Subgraph Counting: Color Coding Beyond Trees.

Venkatesan T. Chakaravarthy, Michael Kapralov, Prakash Murali, Fabrizio Petrini, Xinyu Que, Yogish Sabharwal, Baruch Schieber

Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium, 2016

How to Fake Multiply by a Gaussian Matrix.

Michael Kapralov, Vamsi K. Potluru, David P. Woodruff

Proceedings of the 33nd International Conference on Machine Learning, 2016

2015

Streaming Lower Bounds for Approximating MAX-CUT.

Michael Kapralov, Sanjeev Khanna, Madhu Sudan

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search.

Michael Kapralov

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

2014

Sample-Optimal Fourier Sampling in Any Constant Dimension - Part I.

Piotr Indyk, Michael Kapralov

CoRR, 2014

Approximating matching size from random streams.

Michael Kapralov, Sanjeev Khanna, Madhu Sudan

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

(Nearly) Sample-Optimal Sparse Fourier Transform.

Piotr Indyk, Michael Kapralov, Eric Price

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Spanners and sparsifiers in dynamic streams.

Michael Kapralov, David P. Woodruff

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Sample-Optimal Fourier Sampling in Any Constant Dimension.

Piotr Indyk, Michael Kapralov

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Perfect Matchings in O(nlog n) Time in Regular Bipartite Graphs.

Ashish Goel, Michael Kapralov, Sanjeev Khanna

SIAM J. Comput., 2013

On differentially private low rank approximation.

Michael Kapralov, Kunal Talwar

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Online Submodular Welfare Maximization: Greedy is Optimal.

Michael Kapralov, Ian Post, Jan Vondrák

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Better bounds for matchings in the streaming model.

Michael Kapralov

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Improved lower bounds for matchings in the streaming model

Michael Kapralov

CoRR, 2012

Online and stochastic variants of welfare maximization

Mikhail Kapralov, Ian Post, Jan Vondrák

CoRR, 2012

Single pass sparsification in the streaming model with edge deletions

Ashish Goel, Michael Kapralov, Ian Post

CoRR, 2012

Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service

Debojyoti Dutta, Michael Kapralov, Ian Post, Rajendra Shinde

CoRR, 2012

On the communication and streaming complexity of maximum bipartite matching.

Ashish Goel, Michael Kapralov, Sanjeev Khanna

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Spectral sparsification via random spanners.

Michael Kapralov, Rina Panigrahy

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

NNS Lower Bounds via Metric Expansion for l ∞ and EMD.

Michael Kapralov, Rina Panigrahy

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Embedding Paths into Trees: VM Placement to Minimize Congestion.

Debojyoti Dutta, Michael Kapralov, Ian Post, Rajendra Shinde

Proceedings of the Algorithms - ESA 2012, 2012

2011

Prediction strategies without loss.

Michael Kapralov, Rina Panigrahy

Proceedings of the Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, 2011

Multiplicative Approximations of Random Walk Transition Probabilities.

Michael Kapralov, Rina Panigrahy

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Perfect matchings via uniform sampling in regular bipartite graphs.

Ashish Goel, Michael Kapralov, Sanjeev Khanna

ACM Trans. Algorithms, 2010

Graph Sparsification via Refinement Sampling

Ashish Goel, Michael Kapralov, Sanjeev Khanna

CoRR, 2010

Perfect matchings in o(<i>n</i> log <i>n</i>) time in regular bipartite graphs.

Ashish Goel, Michael Kapralov, Sanjeev Khanna

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Improved Bounds for Online Stochastic Matching.

Bahman Bahmani, Michael Kapralov

Proceedings of the Algorithms, 2010

2009

Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs

Ashish Goel, Michael Kapralov, Sanjeev Khanna

CoRR, 2009

Factor Modeling for Advertisement Targeting.

Ye Chen, Michael Kapralov, Dmitry Pavlov, John F. Canny

Proceedings of the Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, 2009

2008

A Study of 1PI Algorithms for a General Class of Curves.

Mikhail Kapralov, Alexander Katsevich

SIAM J. Imaging Sci., 2008

2007

Filtered Backprojection Inversion of the Cone Beam Transform for a General Class of Curves.

Alexander Katsevich, Mikhail Kapralov

SIAM J. Appl. Math., 2007