Zobrazeno 1 - 10
of 129
pro vyhledávání: '"Raskhodnikova, Sofya"'
We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted over time, and the algorithm is required to update the solution at every
Externí odkaz:
http://arxiv.org/abs/2409.17623
We investigate algorithms for testing whether an image is connected. Given a proximity parameter $\epsilon\in(0,1)$ and query access to a black-and-white image represented by an $n\times n$ matrix of Boolean pixel values, a (1-sided error) connectedn
Externí odkaz:
http://arxiv.org/abs/2312.03681
We study local filters for the Lipschitz property of real-valued functions $f: V \to [0,r]$, where the Lipschitz property is defined with respect to an arbitrary undirected graph $G=(V,E)$. We give nearly optimal local Lipschitz filters both with res
Externí odkaz:
http://arxiv.org/abs/2308.14716
Privacy is a central challenge for systems that learn from sensitive data sets, especially when a system's outputs must be continuously updated to reflect changing data. We consider the achievable error for differentially private continual release of
Externí odkaz:
http://arxiv.org/abs/2306.06723
Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study triangle counting in the noninteractive and interactive local model with
Externí odkaz:
http://arxiv.org/abs/2305.02263
Publikováno v:
In Proceedings of the ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) 2023
We design the first node-differentially private algorithm for approximating the number of connected components in a graph. Given a database representing an $n$-vertex graph $G$ and a privacy parameter $\varepsilon$, our algorithm runs in polynomial t
Externí odkaz:
http://arxiv.org/abs/2304.05890
Autor:
Dhulipala, Laxman, Liu, Quanquan C., Raskhodnikova, Sofya, Shi, Jessica, Shun, Julian, Yu, Shangdi
Differentially private algorithms allow large-scale data analytics while preserving user privacy. Designing such algorithms for graph data is gaining importance with the growth of large networks that model various (sensitive) relationships between in
Externí odkaz:
http://arxiv.org/abs/2211.10887
We initiate an investigation of private sampling from distributions. Given a dataset with $n$ independent observations from an unknown distribution $P$, a sampling algorithm must output a single observation from a distribution that is close in total
Externí odkaz:
http://arxiv.org/abs/2211.08193
We study the accuracy of differentially private mechanisms in the continual release model. A continual release mechanism receives a sensitive dataset as a stream of $T$ inputs and produces, after receiving each input, an accurate output on the obtain
Externí odkaz:
http://arxiv.org/abs/2112.00828
Publikováno v:
Proceedings, Innovations in Theoretical Computer Science (ITCS), 2022
We initiate the study of sublinear-time algorithms that access their input via an online adversarial erasure oracle. After answering each query to the input object, such an oracle can erase $t$ input values. Our goal is to understand the complexity o
Externí odkaz:
http://arxiv.org/abs/2109.08745