2 citations · 2 across the 10 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.DS2023
Lower Bounds on Adaptive Sensing for Matrix Recovery
Praneeth Kacham, David P Woodruff
We study lower bounds on adaptive sensing algorithms for recovering low rank matrices using linear measurements. Given an matrix , a general linear measurement $S(A…
cs.LG2023★ 2 cited
PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels
Praneeth Kacham, Vahab Mirrokni, Peilin Zhong
The quadratic time and memory complexity inherent to self-attention mechanisms, with respect to sequence length, presents a critical computational bottleneck in the training and de…
cs.DS2023
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
Praneeth Kacham, Rasmus Pagh, Mikkel Thorup +1
We revisit Nisan's classical pseudorandom generator (PRG) for space-bounded computation (STOC 1990) and its applications in streaming algorithms. We describe a new generator, HashP…