Publications (59)
Generalized Private Selection and Testing with High Confidence
Edith Cohen, Xin Lyu, Jelani Nelson +2
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 we…
Efficient Distinct Heavy Hitters for DNS DDoS Attack Detection
Yehuda Afek, Anat Bremler-Barr, Edith Cohen +2
Motivated by a recent new type of randomized Distributed Denial of Service (DDoS) attacks on the Domain Name Service (DNS), we develop novel and efficient distinct heavy hitters al…
Estimation for Monotone Sampling: Competitiveness and Customization
Edith Cohen
Random samples are lossy summaries which allow queries posed over the data to be approximated by applying an appropriate estimator to the sample. The effectiveness of sampling, how…
Reverse Ranking by Graph Structure: Model and Scalable Algorithms
Eliav Buchnik, Edith Cohen
Distances in a network capture relations between nodes and are the basis of centrality, similarity, and influence measures. Often, however, the relevance of a node to a node $v…
Stream Sampling for Frequency Cap Statistics
Edith Cohen
Unaggregated data, in streamed or distributed form, is prevalent and come from diverse application domains which include interactions of users with web services and IP traffic. Dat…
Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
Sara Ahmadian, Edith Cohen
Cardinality sketches are popular data structures that enhance the efficiency of working with large data sets. The sketches are randomized representations of sets that are only of l…
Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments
Edith Cohen, Haim Kaplan, Subhabrata Sen
Many data sources are naturally modeled by multiple weight assignments over a set of keys: snapshots of an evolving database at multiple points in time, measurements collected over…
The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for Norm Estimation
Sara Ahmadian, Edith Cohen, Uri Stemmer
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 se…
Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
Edith Cohen, Daniel Delling, Thomas Pajor +1
Propagation of contagion through networks is a fundamental process. It is used to model the spread of information, influence, or a viral infection. Diffusion patterns can be specif…
Urania: Differentially Private Insights into AI Use
Daogao Liu, Edith Cohen, Badih Ghazi +8
We introduce , a novel framework for generating insights about LLM chatbot interactions with rigorous differential privacy (DP) guarantees. The framework employs a private…
Data Reconstruction: When You See It and When You Don't
Edith Cohen, Haim Kaplan, Yishay Mansour +4
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 defini…
Differentially Private Weighted Sampling
Edith Cohen, Ofir Geri, Tamas Sarlos +1
Common datasets have the form of elements with keys (e.g., transactions and products) and the goal is to perform analytics on the aggregated form of key and frequency pairs. A weig…
Truth and Envy in Capacitated Allocation Games
Edith Cohen, Michal Feldman, Amos Fiat +2
We study auctions with additive valuations where agents have a limit on the number of goods they may receive. We refer to such valuations as {\em capacitated} and seek mechanisms t…
Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information
Edith Cohen, Haim Kaplan
Random sampling is an essential tool in the processing and transmission of data. It is used to summarize data too large to store or manipulate and meet resource constraints on band…
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
Idan Attias, Edith Cohen, Moshe Shechner +1
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 ro…
Distance-Based Influence in Networks: Computation and Maximization
Edith Cohen, Daniel Delling, Thomas Pajor +1
A premise at a heart of network analysis is that entities in a network derive utilities from their connections. The {\em influence} of a seed set of nodes is defined as the sum…
Adaptively Robust Resettable Streaming
Edith Cohen, Elena Gribelyuk, Jelani Nelson +1
We study algorithms in the resettable streaming model, where the value of each key can either be increased or reset to zero. The model is suitable for applications such as active r…
Tight Bounds for Answering Adaptively Chosen Concentrated Queries
Emma Rapoport, Edith Cohen, Uri Stemmer
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…
Clustering Small Samples with Quality Guarantees: Adaptivity with One2all pps
Edith Cohen, Shiri Chechik, Haim Kaplan
Clustering of data points is a fundamental tool in data analysis. We consider points in a relaxed metric space, where the triangle inequality holds within a constant factor. Th…
One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
Edith Cohen, Jelani Nelson, Tamás Sarlós +2
Cardinality sketches are compact data structures for representing sets or vectors. These sketches are space-efficient, typically requiring only logarithmic storage in the input siz…
Composable Sketches for Functions of Frequencies: Beyond the Worst Case
Edith Cohen, Ofir Geri, Rasmus Pagh
Recently there has been increased interest in using machine learning techniques to improve classical algorithms. In this paper we study when it is possible to construct compact, co…
Multi-Objective Weighted Sampling
Edith Cohen
{\em Multi-objective samples} are powerful and versatile summaries of large data sets. For a set of keys and associated values , a weighted sample taken with r…
Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity
Eliav Buchnik, Edith Cohen
Graph-based semi-supervised learning (SSL) algorithms predict labels for all nodes based on provided labels of a small set of seed nodes. Classic methods capture the graph structur…
The Target-Charging Technique for Privacy Accounting across Interactive Computations
Edith Cohen, Xin Lyu
We propose the \emph{Target Charging Technique} (TCT), a unified privacy analysis framework for interactive settings where a sensitive dataset is accessed multiple times using diff…
Graph Learning with Loss-Guided Training
Eliav Buchnik, Edith Cohen
Classically, ML models trained with stochastic gradient descent (SGD) are designed to minimize the average loss per example and use a distribution of training examples that remains…
Distance Queries from Sampled Data: Accurate and Efficient
Edith Cohen
Distance queries are a basic tool in data analysis. They are used for detection and localization of change for the purpose of anomaly detection, monitoring, or planning. Distance q…
Envy-Free Makespan Approximation
Edith Cohen, Michal Feldman, Amos Fiat +2
We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-…
On the Robustness of CountSketch to Adaptive Inputs
Edith Cohen, Xin Lyu, Jelani Nelson +3
CountSketch is a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering -hea…
Stream sampling for variance-optimal estimation of subset sums
Edith Cohen, Nick Duffield, Haim Kaplan +2
From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size that we can later use to estimate the total weight of arbitrary subs…
Structure-Aware Sampling: Flexible and Accurate Summarization
Edith Cohen, Graham Cormode, Nick Duffield
In processing large quantities of data, a fundamental problem is to obtain a summary which supports approximate query answering. Random sampling yields flexible summaries which nat…
Semi-Supervised Learning on Graphs through Reach and Distance Diffusion
Edith Cohen
Semi-supervised learning (SSL) is an indispensable tool when there are few labeled entities and many unlabeled entities for which we want to predict labels. With graph-based method…
Hot PATE: Private Aggregation of Distributions for Diverse Task
Edith Cohen, Benjamin Cohen-Wang, Xin Lyu +3
The Private Aggregation of Teacher Ensembles (PATE) framework enables privacy-preserving machine learning by aggregating responses from disjoint subsets of sensitive data. Adaptati…
Sampling Sketches for Concave Sublinear Functions of Frequencies
Edith Cohen, Ofir Geri
We consider massive distributed datasets that consist of elements modeled as key-value pairs and the task of computing statistics or aggregates where the contribution of each key i…
On the Interplay between Incentive Compatibility and Envy Freeness
Edith Cohen, Michal Feldman, Amos Fiat +2
We study mechanisms for an allocation of goods among agents, where agents have no incentive to lie about their true values (incentive compatible) and for which no agent will seek t…
Leveraging Discarded Samples for Tighter Estimation of Multiple-Set Aggregates
Edith Cohen, Haim Kaplan
Many datasets such as market basket data, text or hypertext documents, and sensor observations recorded in different locations or time periods, are modeled as a collection of sets…
Sketch-Based Estimation of Subpopulation-Weight
Edith Cohen, Haim Kaplan
Summaries of massive data sets support approximate query processing over the original data. A basic aggregate over a set of records is the weight of subpopulations specified as a p…
Ãptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen, Xin Lyu, Jelani Nelson +2
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of (for generaliza…
Is Randomness Necessary for Adaptive Data Analysis?
Edith Cohen, Haim Kaplan, Yishay Mansour +2
The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a datase…
Stochastic Matching via Local Sparsification
Sara Ahmadian, Edith Cohen, Mohammad Roghani
The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride…
Self-Similar Epochs: Value in Arrangement
Eliav Buchnik, Edith Cohen, Avinatan Hassidim +1
Optimization of machine learning models is commonly performed through stochastic gradient updates on randomly ordered training examples. This practice means that sub-epochs compris…
Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
Edith Cohen, Mihir Singhal, Uri Stemmer
Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and comp…
Computing Classic Closeness Centrality, at Scale
Edith Cohen, Daniel Delling, Thomas Pajor +1
Closeness centrality, first considered by Bavelas (1948), is an importance measure of a node in a network which is based on the distances from the node to all other nodes. The clas…
What you can do with Coordinated Samples
Edith Cohen, Haim Kaplan
Sample coordination, where similar instances have similar samples, was proposed by statisticians four decades ago as a way to maximize overlap in repeated surveys. Coordinated samp…
Greedy Maximization Framework for Graph-based Influence Functions
Edith Cohen
The study of graph-based submodular maximization problems was initiated in a seminal work of Kempe, Kleinberg, and Tardos (2003): An {\em influence} function of subsets of nodes is…
On the Tradeoff between Stability and Fit
Edith Cohen, Graham Cormode, Nick Duffield +1
In computing, as in many aspects of life, changes incur cost. Many optimization problems are formulated as a one-time instance starting from scratch. However, a common case that ar…
Sample Complexity Bounds for Influence Maximization
Gal Sadeh, Edith Cohen, Haim Kaplan
Influence maximization (IM) is the problem of finding for a given a set of nodes in a network with maximum influence. With stochastic diffusion models, the in…
HyperLogLog Hyper Extended: Sketches for Concave Sublinear Frequency Statistics
Edith Cohen
One of the most common statistics computed over data elements is the number of distinct keys. A thread of research pioneered by Flajolet and Martin three decades ago culminated in…
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
Shiri Chechik, Edith Cohen, Haim Kaplan
The average distance from a node to all other nodes in a graph, or from a query point in a metric space to a set of points, is a fundamental quantity in data analysis. The inverse…
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
Edith Cohen, Jelani Nelson, Tamás Sarlós +1
CountSketch and Feature Hashing (the "hashing trick") are popular randomized dimensionality reduction methods that support recovery of -heavy hitters (keys where $v_i^2…
Probe Scheduling for Efficient Detection of Silent Failures
Edith Cohen, Avinatan Hassidim, Haim Kaplan +3
Most discovery systems for silent failures work in two phases: a continuous monitoring phase that detects presence of failures through probe packets and a localization phase that p…
All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis
Edith Cohen
Graph datasets with billions of edges, such as social and Web graphs, are prevalent, and scalable computation is critical. All-distances sketches (ADS) [Cohen 1997], are a powerful…
A Labeling Approach to Incremental Cycle Detection
Edith Cohen, Amos Fiat, Haim Kaplan +1
In the \emph{incremental cycle detection} problem arcs are added to a directed acyclic graph and the algorithm has to report if the new arc closes a cycle. One seeks to minimize th…
FriendlyCore: Practical Differentially Private Aggregation
Eliad Tsfadia, Edith Cohen, Haim Kaplan +2
Differentially private algorithms for common metric aggregation tasks, such as clustering or averaging, often have limited practicality due to their complexity or to the large numb…
Scaling Embedding Layers in Language Models
Da Yu, Edith Cohen, Badih Ghazi +5
We propose (calable, ontextualized, ffloaded, -gram mbedding), a new method for extending input embedding layers to enhance language model performance. To av…
Variance Competitiveness for Monotone Estimation: Tightening the Bounds
Edith Cohen
Random samples are extensively used to summarize massive data sets and facilitate scalable analytics. Coordinated sampling, where samples of different data sets "share" the randomi…
A Simple and Robust Protocol for Distributed Counting
Edith Cohen, Moshe Shechner, Uri Stemmer
We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across sites while minimizing communication. The…
WOR and 's: Sketches for -Sampling Without Replacement
Edith Cohen, Rasmus Pagh, David P. Woodruff
Weighted sampling is a fundamental tool in data analysis and machine learning pipelines. Samples are used for efficient estimation of statistics or as sparse representations of the…
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries
Edith Cohen, Xin Lyu, Jelani Nelson +2
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…
Differentially-Private Clustering of Easy Instances
Edith Cohen, Haim Kaplan, Yishay Mansour +2
Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify cluster centers without disclosing information on individual…