pith. sign in

Michael Kapralov

Identifiers

  • name variant Michael Kapralov 0.60 · backfill

Papers (28)

  1. Provable Quantization with Randomized Hadamard Transform cs.LG · 2026 · author #3
  2. Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples cs.DS · 2019 · author #1
  3. Online Matching with General Arrivals cs.DS · 2019 · author #2
  4. Faster Spectral Sparsification in Dynamic Streams cs.DS · 2019 · author #1
  5. Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space cs.DS · 2019 · author #1
  6. Dimension-independent Sparse Fourier Transform cs.DS · 2019 · author #1
  7. A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms cs.DS · 2018 · author #2
  8. An Optimal Space Lower Bound for Approximating MAX-CUT cs.DS · 2018 · author #1
  9. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling cs.DS · 2018 · author #2
  10. The Sketching Complexity of Graph and Hypergraph Counting cs.DS · 2018 · author #2
  11. Testing Graph Clusterability: Algorithms and Lower Bounds cs.DS · 2018 · author #2
  12. Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees cs.LG · 2018 · author #2
  13. Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average cs.DS · 2017 · author #1
  14. Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams cs.CC · 2017 · author #1
  15. An Adaptive Sublinear-Time Block Sparse Fourier Transform cs.DS · 2017 · author #2
  16. Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time cs.DS · 2016 · author #1
  17. Subgraph Counting: Color Coding Beyond Trees cs.DC · 2016 · author #2
  18. Streaming Lower Bounds for Approximating MAX-CUT cs.DS · 2014 · author #1
  19. Single Pass Spectral Sparsification in Dynamic Streams cs.DS · 2014 · author #1
  20. Sample-Optimal Fourier Sampling in Any Constant Dimension -- Part I cs.DS · 2014 · author #2
  21. Online submodular welfare maximization: Greedy is optimal cs.DS · 2012 · author #1
  22. Single pass sparsification in the streaming model with edge deletions cs.DS · 2012 · author #2
  23. Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service cs.NI · 2012 · author #2
  24. Prediction strategies without loss cs.DS · 2010 · author #1
  25. Graph Sparsification via Refinement Sampling cs.DS · 2010 · author #2
  26. Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs cs.DS · 2009 · author #2
  27. Perfect Matchings in \~O(n^{1.5}) Time in Regular Bipartite Graphs cs.DS · 2009 · author #2
  28. Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs cs.DS · 2008 · author #2

Mentions

  • 1403.5804 #2 · backfill · confidence 0.70 Michael Kapralov
  • 1204.1025 #1 · backfill · confidence 0.70 Michael Kapralov
  • 1203.4900 #2 · backfill · confidence 0.70 Michael Kapralov
  • 1202.3683 #2 · backfill · confidence 0.70 Michael Kapralov
  • 1008.3672 #1 · backfill · confidence 0.70 Michael Kapralov
  • 1004.4915 #2 · backfill · confidence 0.70 Michael Kapralov
  • 0909.3346 #2 · backfill · confidence 0.70 Michael Kapralov
  • 0902.1617 #2 · backfill · confidence 0.70 Michael Kapralov
  • 0811.2457 #2 · backfill · confidence 0.70 Michael Kapralov

Frequent Coauthors