15 citations · 24 across the 15 of their papers we have counts for
21 papers
An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting
Jalaj Upadhyay
The goal of this note is to give a detailed proof, to the best of our understanding, of the recent presentation by Harrison and Leeman (arXiv:2609.17650v01 and arXiv:2609.17650v02)…
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…
Correlated Noise Mechanisms for Differentially Private Learning
Krishna Pillutla, Jalaj Upadhyay, Christopher A. Choquette-Choo +9
This monograph explores the design and analysis of correlated noise mechanisms for differential privacy (DP), focusing on their application to private training of AI and machine le…
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,…
Continual Counting with Gradual Privacy Expiration
Joel Daniel Andersson, Monika Henzinger, Rasmus Pagh +2
Differential privacy with gradual expiration models the setting where data items arrive in a stream and at a given time the privacy loss guaranteed for a data item seen at time…
Differentially Private Decentralized Learning with Random Walks
Edwige Cyffers, Aurélien Bellet, Jalaj Upadhyay
The popularity of federated learning comes from the possibility of better scalability and the ability for participants to keep control of their data, improving data security and so…
A Unifying Framework for Differentially Private Sums under Continual Observation
Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay
We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for…
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…
Almost Tight Error Bounds on Differentially Private Continual Counting
Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay
The first large-scale deployment of private federated learning uses differentially private counting in the continual release model as a subroutine (Google AI blog titled "Federated…
Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization
Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay
In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for…
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…
A Framework for Private Matrix Analysis
Jalaj Upadhyay, Sarvagya Upadhyay
We study private matrix analysis in the sliding window model where only the last updates to matrices are considered useful for analysis. We give first efficient space di…
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…
Multi-prover Proof-of-Retrievability
Maura B. Paterson, Douglas R. Stinson, Jalaj Upadhyay
There has been considerable recent interest in "cloud storage" wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actua…
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…
A coding theory foundation for the analysis of general unconditionally secure proof-of-retrievability schemes for cloud storage
Maura B. Paterson, Douglas R. Stinson, Jalaj Upadhyay
There has been considerable recent interest in "cloud storage" wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actua…