Zobrazeno 1 - 10
of 460
pro vyhledávání: '"HENZINGER, MONIKA"'
Dynamically maintaining the minimum cut in a graph $G$ under edge insertions and deletions is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an $n$-node graph the best known
Externí odkaz:
http://arxiv.org/abs/2412.15069
Autor:
Henzinger, Monika, Upadhyay, Jalaj
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, according to Google, has over a billion users. More specifically, Goog
Externí odkaz:
http://arxiv.org/abs/2412.02840
A series of recent works by Lyu, Wang, Vadhan, and Zhang (TCC `21, NeurIPS `22, STOC `23) showed that composition theorems for non-interactive differentially private mechanisms extend to the concurrent composition of interactive differentially privat
Externí odkaz:
http://arxiv.org/abs/2411.03299
Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum fli
Externí odkaz:
http://arxiv.org/abs/2408.11637
We study in this paper the problem of maintaining a solution to $k$-median and $k$-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy
Externí odkaz:
http://arxiv.org/abs/2406.19926
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricac
Externí odkaz:
http://arxiv.org/abs/2406.14111
As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local
Externí odkaz:
http://arxiv.org/abs/2406.11649
Autor:
Andersson, Joel Daniel, Henzinger, Monika, Pagh, Rasmus, Steiner, Teresa Anna, Upadhyay, Jalaj
Differential privacy with gradual expiration models the setting where data items arrive in a stream and at a given time $t$ the privacy loss guaranteed for a data item seen at time $(t-d)$ is $\epsilon g(d)$, where $g$ is a monotonically non-decreasi
Externí odkaz:
http://arxiv.org/abs/2406.03802
Autor:
Axiotis, Kyriakos, Cohen-Addad, Vincent, Henzinger, Monika, Jerome, Sammy, Mirrokni, Vahab, Saulpic, David, Woodruff, David, Wunder, Michael
We study the data selection problem, whose aim is to select a small representative subset of data that can be used to efficiently train a machine learning model. We present a new data selection approach based on $k$-means clustering and sensitivity s
Externí odkaz:
http://arxiv.org/abs/2402.17327
Computing the core decomposition of a graph is a fundamental problem that has recently been studied in the differentially private setting, motivated by practical applications in data mining. In particular, Dhulipala et al. [FOCS 2022] gave the first
Externí odkaz:
http://arxiv.org/abs/2402.18020