3 papers
cs.DS2026
A Matrix Factorization Approach in Turnstile Streaming
Jan Bulanek, Ravi Kumar, Raghu Meka +2
We define the -point query problem in data streams. Given a fixed matrix , the goal is to maintain a vector under turnstile updates and answer each query with an esti…
cs.DS2026
On the LSH Distortion of Ulam and Cayley Similarities
Flavio Chierichetti, Mirko Giacchini, Ravi Kumar +1
Locality-sensitive hashing (LSH) has found widespread use as a fundamental primitive, particularly to accelerate nearest neighbor search. An LSH scheme for a similarity function $S…
cs.DS2026
Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
Lynn Chua, Badih Ghazi, Ravi Kumar +3
We study the problem of Stochastic Convex Optimization (SCO) under the constraint of local Label Differential Privacy (L-LDP). In this setting, the features are considered public,…