15 citations · 24 across the 15 of their papers we have counts for
11 papers · 1 filter
Near-Optimal Generalized Private Testing
Anamay Chaturvedi, Monika Henzinger, Jalaj Upadhyay
In differential privacy (DP), the generalized private testing problem was introduced by Liu and Talwar (STOC 2019). Given a dataset and a sequence of black-box…
Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting
Monika Henzinger, Nikita P. Kalinin, Jalaj Upadhyay
The factorization norms of the lower-triangular all-ones matrix, and , play a central role in differential privacy as they are used…
Binned Group Algebra Factorization for Differentially Private Continual Counting
Monika Henzinger, Nikita P. Kalinin, Jalaj Upadhyay
We study memory-efficient matrix factorization for differentially private counting under continual observation. While recent work by Henzinger and Upadhyay 2024 introduced a factor…
Improved Differentially Private Continual Observation Using Group Algebra
Monika Henzinger, Jalaj Upadhyay
Differentially private weighted prefix sum under continual observation is a crucial component in the production-level deployment of private next-word prediction for Gboard, which,…
Differentially Private Range Query on Shortest Paths
Chengyuan Deng, Jie Gao, Jalaj Upadhyay +1
We consider differentially private range queries on a graph where query ranges are defined as the set of edges on a shortest path of the graph. Edges in the graph carry sensitive a…
Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
Hendrik Fichtenberger, Monika Henzinger, Jalaj Upadhyay
We study fine-grained error bounds for differentially private algorithms for counting under continual observation. Our main insight is that the matrix mechanism when using lower-tr…
Near Optimal Linear Algebra in the Online and Sliding Window Models
Vladimir Braverman, Petros Drineas, Cameron Musco +4
We initiate the study of numerical linear algebra in the sliding window model, where only the most recent updates in a stream form the underlying data set. We first introduce a…
On Low-Space Differentially Private Low-rank Factorization in the Spectral Norm
Jalaj Upadhyay
Low-rank factorization is used in many areas of computer science where one performs spectral analysis on large sensitive data stored in the form of matrices. In this paper, we stud…
The Price of Differential Privacy for Low-Rank Factorization
Jalaj Upadhyay
In this paper, we study what price one has to pay to release {\em differentially private low-rank factorization} of a matrix. We consider various settings that are close to the rea…
Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
Jalaj Upadhyay
The Johnson-Lindenstrauss property ({\sf JLP}) of random matrices has immense application in computer science ranging from compressed sensing, learning theory, numerical linear alg…
Differentially Private Linear Algebra in the Streaming Model
Jalaj Upadhyay
Numerical linear algebra plays an important role in computer science. In this paper, we initiate the study of performing linear algebraic tasks while preserving privacy when the da…