research
∙
04/13/2023
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
We revisit Nisan's classical pseudorandom generator (PRG) for space-boun...
share
research
∙
12/01/2022
Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
Kernel matrices, as well as weighted graphs represented by them, are ubi...
research
∙
04/13/2022
Sketching Algorithms and Lower Bounds for Ridge Regression
We give a sketching-based iterative algorithm that computes 1+ε approxim...
research
∙
07/16/2021
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
Currently, in the numerical linear algebra community, it is thought that...
research
∙
11/09/2020
Reduced-Rank Regression with Operator Norm Error
A common data analysis task is the reduced-rank regression problem: ...
research
∙
12/27/2019