Uri Stemmer
YOU?
Author Swipe
View article: A Simple and Robust Protocol for Distributed Counting
A Simple and Robust Protocol for Distributed Counting Open
We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across $k$ sites while minimizing communication. The communication complexity of this problem is known to be $Θ(…
View article: The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation Open
Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the black-box adversarial setting, where a fixed, hidden sketching matrix $A \in R^{k \…
View article: Tight Bounds for Answering Adaptively Chosen Concentrated Queries
Tight Bounds for Answering Adaptively Chosen Concentrated Queries Open
Most work on adaptive data analysis assumes that samples in the dataset are independent. When correlations are allowed, even the non-adaptive setting can become intractable, unless some structural constraints are imposed. To address this, …
View article: Bayesian Perspective on Memorization and Reconstruction
Bayesian Perspective on Memorization and Reconstruction Open
We introduce a new Bayesian perspective on the concept of data reconstruction, and leverage this viewpoint to propose a new security definition that, in certain settings, provably prevents reconstruction attacks. We use our paradigm to she…
View article: Nearly Optimal Sample Complexity for Learning with Label Proportions
Nearly Optimal Sample Complexity for Learning with Label Proportions Open
We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each bag are available. Despite the partial observability, the g…
View article: Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries Open
Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and computational costs. However, recent research has shown that th…
View article: Data Reconstruction: When You See It and When You Don't
Data Reconstruction: When You See It and When You Don't Open
We revisit the fundamental question of formally defining what constitutes a reconstruction attack. While often clear from the context, our exploration reveals that a precise definition is much more nuanced than it appears, to the extent th…
View article: One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches Open
Cardinality sketches are compact data structures for representing sets or vectors. These sketches are space-efficient, typically requiring only logarithmic storage in the input size, and enable approximation of cardinality (or the number o…
View article: On Differentially Private Linear Algebra
On Differentially Private Linear Algebra Open
We introduce efficient differentially private (DP) algorithms for several linear algebraic tasks, including solving linear equalities over arbitrary fields, linear inequalities over the reals, and computing affine spans and convex hulls. A…
View article: A Framework for Adversarial Streaming Via Differential Privacy and Difference Estimators
A Framework for Adversarial Streaming Via Differential Privacy and Difference Estimators Open
Classical streaming algorithms operate under the (not always reasonable) assumption that the input stream is fixed in advance. Recently, there is a growing interest in designing robust streaming algorithms that provide provable guarantees …
View article: Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries Open
One of the most basic problems for studying the "price of privacy over time" is the so called private counter problem, introduced by Dwork et al. (2010) and Chan et al. (2010). In this problem, we aim to track the number of events that occ…
View article: Private Truly-Everlasting Robust-Prediction
Private Truly-Everlasting Robust-Prediction Open
Private Everlasting Prediction (PEP), recently introduced by Naor et al. [2023], is a model for differentially private learning in which the learner never publicly releases a hypothesis. Instead, it provides black-box access to a "predicti…
View article: Hot PATE: Private Aggregation of Distributions for Diverse Task
Hot PATE: Private Aggregation of Distributions for Diverse Task Open
The Private Aggregation of Teacher Ensembles (PATE) framework enables privacy-preserving machine learning by aggregating responses from disjoint subsets of sensitive data. Adaptations of PATE to tasks with inherent output diversity such as…
View article: Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs Open
CountSketch and Feature Hashing (the ``hashing trick'') are popular randomized dimensionality reduction methods that support recovery of l2 -heavy hitters and approximate inner products. When the inputs are not adaptive (do not depend on p…
View article: Adaptive Data Analysis in a Balanced Adversarial Model
Adaptive Data Analysis in a Balanced Adversarial Model Open
In adaptive data analysis, a mechanism gets $n$ i.i.d. samples from an unknown distribution $D$, and is required to provide accurate estimations to a sequence of adaptively chosen statistical queries with respect to $D$. Hardt and Ullman (…
View article: Private Everlasting Prediction
Private Everlasting Prediction Open
A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points while protecting the privacy of the training set [Kasiviswannathan et al., FOCS 2008].…
View article: Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization Open
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of O(ξ−1 log(1/β)) (for generalization error ξ with confidence 1−β). The private version of the probl…
View article: On Differentially Private Online Predictions
On Differentially Private Online Predictions Open
In this work we introduce an interactive variant of joint differential privacy towards handling online processes in which existing privacy definitions seem too restrictive. We study basic properties of this definition and demonstrate that …
View article: On Differential Privacy and Adaptive Data Analysis with Bounded Space
On Differential Privacy and Adaptive Data Analysis with Bounded Space Open
We study the space complexity of the two related fields of differential privacy and adaptive data analysis. Specifically, (1) Under standard cryptographic assumptions, we show that there exists a problem P that requires exponentially more …
View article: Concurrent Shuffle Differential Privacy Under Continual Observation
Concurrent Shuffle Differential Privacy Under Continual Observation Open
We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batches of users. Similarly to the standard (single) shuffle mo…
View article: A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators Open
Classical streaming algorithms operate under the (not always reasonable) assumption that the input stream is fixed in advance. Recently, there is a growing interest in designing robust streaming algorithms that provide provable guarantees …
View article: Relaxed Models for Adversarial Streaming: The Bounded Interruptions Model and the Advice Model
Relaxed Models for Adversarial Streaming: The Bounded Interruptions Model and the Advice Model Open
Streaming algorithms are typically analyzed in the oblivious setting, where we assume that the input stream is fixed in advance. Recently, there is a growing interest in designing adversarially robust streaming algorithms that must maintai…
View article: Generalized Private Selection and Testing with High Confidence
Generalized Private Selection and Testing with High Confidence Open
Composition theorems are general and powerful tools that facilitate privacy accounting across multiple data accesses from per-access privacy bounds. However they often result in weaker bounds compared with end-to-end analysis. Two popular …
View article: Differentially-Private Bayes Consistency
Differentially-Private Bayes Consistency Open
We construct a universally Bayes consistent learning rule that satisfies differential privacy (DP). We first handle the setting of binary classification and then extend our rule to the more general setting of density estimation (with respe…
View article: Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization Open
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of $O(ξ^{-1} \log(1/β))$ (for generalization error $ξ$ with confidence $1-β$). The private version of…
View article: Adversarially Robust Streaming Algorithms via Differential Privacy
Adversarially Robust Streaming Algorithms via Differential Privacy Open
A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary . We establish a connection between adversarial robustness of stre…
View article: MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably
MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably Open
In this work, we introduce the Gulliver multi-party computation model (GMPC). The GMPC model considers a single highly powerful party, called the server or Gulliver, that is connected to $n$ users over a star topology network (alternativel…
View article: Differentially Private Learning of Geometric Concepts
Differentially Private Learning of Geometric Concepts Open
We present differentially private efficient algorithms for learning union of polygons in the plane (which are not necessarily convex). Our algorithms achieve $(α,β)$-PAC learning and $(ε,δ)$-differential privacy using a sample of size $\ti…
View article: Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs Open
CountSketch and Feature Hashing (the "hashing trick") are popular randomized dimensionality reduction methods that support recovery of $\ell_2$-heavy hitters (keys $i$ where $v_i^2 > ε\|\boldsymbol{v}\|_2^2$) and approximate inner products…
View article: On the Robustness of CountSketch to Adaptive Inputs
On the Robustness of CountSketch to Adaptive Inputs Open
CountSketch is a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering $\ell_2$-heavy hitters of a vector (entries with $v[i]^2 \geq \frac{1}{…