Praneeth Kacham

Research

Preprints

• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
  with Ravindran Kannan, Chiranjib Bhattacharyya and David P. Woodruff
  arXiv
• Differentially Private Vertical Federated Learning Primitives
  with Vincent Cohen-Addad, Vahab Mirrokni and Peilin Zhong

Published

• Approximating the Top Eigenvector in Random Order Streams
  with David P. Woodruff
  NeurIPS 2024. Selected as a spotlight.
• Faster Algorithms for Schatten-p Low Rank Approximation
  with David P. Woodruff
  RANDOM 2024 arXiv
• PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels
  with Vahab Mirrokni and Peilin Zhong
  ICML 2024 arXiv
• High-Dimensional Geometric Streaming for Almost Low Rank Data
  with Hossein Esfandiari, Vahab Mirrokni, David P. Woodruff and Peilin Zhong
  ICML 2024 arXiv
• Optimal Communication Bounds for Classic Functions in Coordinator model and Beyond
  with Hossein Esfanidari, Vahab Mirrokni, David P. Woodruff and Peilin Zhong
  STOC 2024 arXiv
• Lower Bounds on Adaptive Sensing for Matrix Recovery
  with David P. Woodruff
  NeurIPS 2023 arXiv
• Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
  with Rasmus Pagh, Mikkel Thorup and David P. Woodruff
  FOCS 2023 arXiv Slides
• Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation
  with Ainesh Bakshi, Piotr Indyk, Sandeep Silwal and Samson Zhou
  ICLR 2023 arXiv
• Sketching Algorithms and Lower Bounds for Ridge Regression
  with David P. Woodruff
  ICML 2022 arXiv Slides
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
  with Nadiia Chepurko, Kenneth L. Clarkson and David P. Woodruff
  SODA 2022 arXiv Slides
• Reduced-Rank Regression with Operator Norm Error
  with David P. Woodruff
  COLT 2021 arXiv Slides
• Dimensionality Reduction for Sum-of-Distances Metric
  with Zhili Feng and David P. Woodruff
  ICML 2021. Selected for long talk arXiv Slides
• Robust k-means++
  with Amit Deshpande and Rameshwar Pratap
  UAI 2020
• Optimal Deterministic Coresets for Ridge Regression
  with David P. Woodruff
  AISTATS 2020 Slides