MK
Michael Kapralov
cs.DScs.LGcs.NAmath.NAcs.DCcs.DMstat.MLcs.AIcs.CCcs.DB
On Valency
published · living versionsW_84x4trpk·v1 · currentpublished
Attention under Bounded Key-Query Similarity: Space Complexity and Transformer Anisotropy
with Justin Y. Chen, Ying Feng, Piotr Indyk, Ekaterina Kochetkova +1
1 version
Preprints & journals
62 papers in the corpus · 2008–2026Constant-Factor Local Approximation for Bipartite Densest Subgraph2610.24114v1 · Michael Kapralov, Jakub \Lacki, Silvio Lattanzi et al.2026 · 0 citationsarXiv
Towards Tight Bounds for Streaming Attention2606.07205v1 · Justin Y. Chen, Ying Feng, Piotr Indyk et al.2026 · 0 citationsarXiv
Recovering Communities in Structured Random Graphs2601.16910v1 · Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska2026 · 0 citationsarXiv
Spectral Clustering in Birthday Paradox Time2601.05883v1 · Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska2026 · 0 citationsarXiv
Sublinear Time Low-Rank Approximation of Hankel Matrices2511.21418v1 · Michael Kapralov, Cameron Musco, Kshiteej Sheth2025 · 1 citationarXiv
Spectral Clustering with Side Information2511.17326v1 · Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova et al.2025 · 0 citationsarXiv
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs2510.17740v1 · Shunhua Jiang, Michael Kapralov, Lawrence Li et al.2025 · 0 citationsarXiv
Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions2507.23539v1 · Piotr Indyk, Michael Kapralov, Kshiteej Sheth et al.2025 · 0 citationsarXiv
Streaming Attention Approximation via Discrepancy Theory2502.07861v3 · Ekaterina Kochetkova, Kshiteej Sheth, Insu Han et al.2025 · 0 citationsarXiv
On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models2412.14315v1 · Aditya Bhaskara, Agastya Vibhuti Jha, Michael Kapralov et al.2024 · 0 citationsarXiv
On the Streaming Complexity of Expander Decomposition2404.16701v2 · Yu Chen, Michael Kapralov, Mikhail Makarov et al.2024 · 0 citationsarXiv
Streaming Algorithms for Connectivity Augmentation2402.10806v1 · Ce Jin, Michael Kapralov, Sepideh Mahabadi et al.2024 · 0 citationsarXiv
On the adversarial robustness of Locality-Sensitive Hashing in Hamming space2402.09707v3 · Michael Kapralov, Mikhail Makarov, Christian Sohler2024 · 3 citationsarXiv
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations2401.02562v1 · Moses Charikar, Michael Kapralov, Erik Waingarten2024 · 2 citationsarXiv
Toeplitz Low-Rank Approximation with Sublinear Query Complexity2211.11328v1 · Michael Kapralov, Hannah Lawrence, Mikhail Makarov et al.2022 · 1 citationarXiv
Expander Decomposition in Dynamic Streams2211.11384v3 · Arnold Filtser, Michael Kapralov, Mikhail Makarov2022 · 0 citationsarXiv
On Constructing Spanners from Random Gaussian Projections2209.14775v1 · Sepehr Assadi, Michael Kapralov, Huacheng Yu2022 · 0 citationsarXiv
Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds2207.02581v3 · Michael Kapralov, Akash Kumar, Silvio Lattanzi et al.2022 · 0 citationsarXiv
Motif Cut Sparsifiers2204.09951v2 · Michael Kapralov, Mikhail Makarov, Sandeep Silwal et al.2022 · 0 citationsarXiv
Simulating Random Walks in Random Streams2112.07532v1 · John Kallaugher, Michael Kapralov, Eric Price2021 · 3 citationsarXiv
Efficient and Local Parallel Random Walks2112.00655v1 · Michael Kapralov, Silvio Lattanzi, Navid Nouri et al.2021 · 1 citationarXiv
Factorial Lower Bounds for (Almost) Random Order Streams2110.10091v3 · Ashish Chiplunkar, John Kallaugher, Michael Kapralov et al.2021 · 0 citationsarXiv
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms2107.07347v2 · Karl Bringmann, Michael Kapralov, Mikhail Makarov et al.2021 · 1 citationarXiv
Noisy Boolean Hidden Matching with Applications2107.02578v2 · Michael Kapralov, Amulya Musipatla, Jakab Tardos et al.2021 · 1 citationarXiv
Spectral Hypergraph Sparsifiers of Nearly Linear Size2106.02353v1 · Michael Kapralov, Robert Krauthgamer, Jakab Tardos et al.2021 · 14 citationsarXiv
Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model2103.11669v1 · Michael Kapralov2021 · 17 citationsarXiv
Spectral Clustering Oracles in Sublinear Time2101.05549v2 · Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi et al.2021 · 1 citationarXiv
Kernel Density Estimation through Density Constrained Near Neighbor Search2011.06997v1 · Moses Charikar, Michael Kapralov, Navid Nouri et al.2020 · 10 citationsarXiv
Communication Efficient Coresets for Maximum Matching2011.06481v1 · Michael Kapralov, Gilbert Maystre, Jakab Tardos2020 · 1 citationarXiv
Towards Tight Bounds for Spectral Sparsification of Hypergraphs2011.06530v2 · Michael Kapralov, Robert Krauthgamer, Jakab Tardos et al.2020 · 18 citationsarXiv
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model2007.14204v2 · Arnold Filtser, Michael Kapralov, Navid Nouri2020 · 19 citationsarXiv
Scaling up Kernel Ridge Regression via Locality Sensitive Hashing2003.09756v1 · Michael Kapralov, Navid Nouri, Ilya Razenshteyn et al.2020 · 5 citationsarXiv
Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems1912.12740v4 · Maciej Besta, Marc Fischer, Vasiliki Kalavri et al.2019 · 57 citationsIEEE Transactions on Parallel and Distributed Systems (TPDS), 2022
Oblivious Sketching of High-Degree Polynomial Kernels1909.01410v5 · Thomas D. Ahle, Michael Kapralov, Jakob B. T. Knudsen et al.2019 · 44 citationsarXiv
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples1907.05725v1 · Michael Kapralov, Slobodan Mitrovi'c, Ashkan Norouzi-Fard et al.2019 · 29 citationsarXiv
Online Matching with General Arrivals1904.08255v1 · Buddhima Gamlath, Michael Kapralov, Andreas Maggiori et al.2019 · 58 citationsarXiv
Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space1903.12150v1 · Michael Kapralov, Navid Nouri, Aaron Sidford et al.2019 · 9 citationsarXiv
Faster Spectral Sparsification in Dynamic Streams1903.12165v1 · Michael Kapralov, Aida Mousavifar, Cameron Musco et al.2019 · 3 citationsarXiv
Dimension-independent Sparse Fourier Transform1902.10633v1 · Michael Kapralov, Ameya Velingker, Amir Zandieh2019 · 20 citationsarXiv
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms1812.08723v1 · Haim Avron, Michael Kapralov, Cameron Musco et al.2018 · 29 citationsarXiv
An Optimal Space Lower Bound for Approximating MAX-CUT1811.10879v1 · Michael Kapralov, Dmitry Krachun2018 · 22 citationsarXiv
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling1811.07780v1 · Sepehr Assadi, Michael Kapralov, Sanjeev Khanna2018 · 36 citationsarXiv
The Sketching Complexity of Graph and Hypergraph Counting1808.04995v1 · John Kallaugher, Michael Kapralov, Eric Price2018 · 20 citationsarXiv
Testing Graph Clusterability: Algorithms and Lower Bounds1808.04807v2 · Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna et al.2018 · 18 citationsarXiv
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees1804.09893v2 · Haim Avron, Michael Kapralov, Cameron Musco et al.2018 · 84 citationsarXiv
Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average1708.04544v2 · Michael Kapralov2017 · 27 citationsarXiv
Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams1704.00633v1 · Michael Kapralov, Jelani Nelson, Jakub Pachocki et al.2017 · 28 citationsarXiv
An Adaptive Sublinear-Time Block Sparse Fourier Transform1702.01286v2 · Volkan Cevher, Michael Kapralov, Jonathan Scarlett et al.2017 · 14 citationsarXiv
How to Fake Multiply by a Gaussian Matrix1606.05732v2 · Michael Kapralov, Vamsi K. Potluru, David P. Woodruff2016 · 13 citationsarXiv
Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time1604.00845v1 · Michael Kapralov2016 · 27 citationsarXiv
Career total: 119 works. 62 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.