Praneeth Kacham

Hello! I am a Research Scientist in the Algorithms and Optimization team at Google Research NYC. I finished my PhD at Carnegie Mellon University and was advised by Prof. David P. Woodruff. Before that, I was an undergrad at IIT Delhi. I am interested in algorithms for all sorts of problems, mainly randomized algorithms for Numerical Linear Algebra and matrix methods in Big Data settings.
Email: letter p followed by lastname at google dot com, me at firstname lastname dot com

Thesis

Research

Preprints

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

Published

  1. Approximating the Top Eigenvector in Random Order Streams
    with David P. Woodruff
    NeurIPS 2024. Selected as a spotlight.
  2. Faster Algorithms for Schatten-p Low Rank Approximation
    with David P. Woodruff
    RANDOM 2024 arXiv
  3. PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels
    with Vahab Mirrokni and Peilin Zhong
    ICML 2024 arXiv
  4. High-Dimensional Geometric Streaming for Almost Low Rank Data
    with Hossein Esfandiari, Vahab Mirrokni, David P. Woodruff and Peilin Zhong
    ICML 2024 arXiv
  5. 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
  6. Lower Bounds on Adaptive Sensing for Matrix Recovery
    with David P. Woodruff
    NeurIPS 2023 arXiv
  7. Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
    with Rasmus Pagh, Mikkel Thorup and David P. Woodruff
    FOCS 2023 arXiv Slides
  8. Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation
    with Ainesh Bakshi, Piotr Indyk, Sandeep Silwal and Samson Zhou
    ICLR 2023 arXiv
  9. Sketching Algorithms and Lower Bounds for Ridge Regression
    with David P. Woodruff
    ICML 2022 arXiv Slides
  10. 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
  11. Reduced-Rank Regression with Operator Norm Error
    with David P. Woodruff
    COLT 2021 arXiv Slides
  12. Dimensionality Reduction for Sum-of-Distances Metric
    with Zhili Feng and David P. Woodruff
    ICML 2021. Selected for long talk arXiv Slides
  13. Robust k-means++
    with Amit Deshpande and Rameshwar Pratap
    UAI 2020
  14. Optimal Deterministic Coresets for Ridge Regression
    with David P. Woodruff
    AISTATS 2020 Slides
Last Updated : November 2024