Edith Cohen
I am a Research Scientist at Google (Mountain View, CA) since 2015. I am also a (visiting) full professor at the School of Computer Science at Tel Aviv University in Israel. I attended
Tel Aviv University
(Israel)
for my undergraduate studies in math, physics, and
computer science, graduating in 1985, and continued to obtain an M.Sc.
in computer science in 1986, supervised by Michael Tarsi. I then headed to
Stanford, CA, where I
worked on a Ph.D. in Computer
Science,
with
Andrew Goldberg and Nimrod Megiddo, graduating in 1991.
From 1991 to 2012, I was a member of the research staff, first at the
legendary AT&T Bell Laboratories , and after a 1997 split, at AT&T Labs Research. In 1997 I also visited the Computer Science Division at UC Berkeley. From 2012 to 2014 I was a principal researcher at Microsoft Research (Silicon Valley).
My research interests include Algorithms design, Data Mining, Machine Learning, Optimization, Networks, and more. I prefer a principled approach to modeling and design and I am always looking to learn and expand my horizons. In the span of my research career, I developed models and scalable algorithms in a wide range of areas including query processing and optimization, data summarization, content search and delivery, caching, prefetching, routing, streaming and distributed computation, fundamental graph algorithms and scalable mining of massive graphs. My work enables the leveraging of much larger data sets than previously possible. More details on my work can be found on my personal web page.
Research Areas
Authored Publications
Sort By
Preview abstract
We study algorithms in the resettable streaming model, where the value of each key can either be increased or reset to zero. This model is suitable for applications such as active resource monitoring with support for deletions and machine unlearning. We show that all existing sketches for this model are vulnerable to adaptive adversarial attacks that apply even when the sketch size is polynomial in the length of the stream. To overcome these vulnerabilities, we present the first adaptively robust sketches for resettable streams that require only polylogarithmic space complexity in the stream length. Our framework supports (sub) linear statistics including $L_p$ moments for $p\in[0,1]$ (in particular, Cardinality and Sum) and Bernstein statistics. We bypass strong impossibility results known for linear and composable sketches by designing dedicated single-stream sketches robustified via Differential Privacy. Unlike standard robustification techniques, which provide limited benefits in this setting and still require polynomial space in the stream length, we leverage the Binary Tree Mechanism for continual observation to protect the sketch's internal randomness. This enables accurate prefix-max error guarantees with polylogarithmic space.
View details
Preview abstract
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 of nonzero entries). A crucial property in applications is \emph{composability} of the sketching map, meaning that the sketch of a union of sets can be computed from individual sketches. Existing designs provide strong statistical guarantees, ensuring that a randomly sampled sketching map is accurate with high probability for a number of queries that is exponential in the sketch size $k$. However, these guarantees degrade to quadratic in $k$ when queries are adaptive, meaning they depend on previous responses.
Prior works on statistical queries (Steinke and Ullman, 2015) and specific MinHash cardinality sketches (Ahmadian and Cohen, 2024) established that this is tight in that they can be compromised using $\tilde{O}(k^2)$ adaptive queries. In this work, we develop a unified attack framework that applies to broad classes of cardinality sketches. We show that any union-composable sketching map can be compromised with $\tilde{O}(k^4)$ adaptive queries. Moreover, this improves to a tight bound of $\tilde{O}(k^2)$ for monotone composable maps (special cases include MinHash, statistical queries, Boolean linear maps), for any linear map over the reals $\mathbb{R}$ and finite fields $\mathbb{F}_p$, and for any linear map over the integers $\mathbb{Z}$ but when the estimator may only use the nonzero structure of the sketch (as in Cormode et al., 2003). Our work is the first to apply to general composable maps and establishes and builds on fundamental properties of these structures. Specifically for linear sketches, we are the first to establish tight quadratic bounds, to any subclass, and our bounds strengthen weaker polynomial bounds recently established by Gribelyuk et al. (2024).
View details
Preview abstract
The classic online stochastic matching problem typically requires immediate and
irrevocable matching decisions. However, in many modern decentralized systems
such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match
itself. We formalize this challenge by introducing a two-stage local sparsification
framework. In this setting, arriving requests must prune their realized compatibility
sets to a strict budget of k edges before a central coordinator optimizes the global
matching. This creates a ”middle ground” between local information constraints
and global optimization utility.
We propose a local selection strategy, parametrized by a fractional solution of the
expected instance. Theoretically, we quantify the approximation ratio as a function
of the solution’s spread. We prove that under sufficient spread, our sparsifier
globally preserves the expected size of the maximum matching. Empirically,
we demonstrate the robustness of our approach using the New York City ridehailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.
View details
Online Differentially Private Clustering: Private to Non-Private Reduction
Vadym Doroshenko
Pritish Kamath
Alexander Knop
Ethan Leeman
Adam Sealfon
NeurIPS (2026)
Preview abstract
We study differentially private k-mean/median clustering in the online streaming setting where a point arrive at each time step and we need to output a set of k centers that optimize the k-mean/median objective of all the points so far. We give a generic transformation that turns the sensitive stream into a differentially private stream, which is a semi-coreset of the original stream and allows us to run any (non-private) online clustering algorithm as a post-processing step. Our algorithm is efficient in terms of errors, space and running time compared to existing algorithms (Epasto et al., 2023; Dupr{\'{e}} la Tour, 2024). Furthermore, our reduction allows us to inherit properties of the non-private clustering, such as consistency (Lattanzi and Vassilvitski, 2017), which was not satisfied by previous DP algorithms.
View details
Preview abstract
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 $\Theta(\frac{k}{\eps}\log N)$ for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to $\Theta(\frac{\sqrt{k}}{\eps}\log N)$, but their analysis is restricted to the oblivious setting, where the stream of events is independent of the protocol's outputs.
Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a polylog(k) factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust?
We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of $O(\frac{\sqrt{k}}{\eps} \log N)$. Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting.
View details
Preview abstract
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 text generation, where the desired output is a sample from a distribution, face a core tension: as diversity increases, samples from different teachers are less likely to agree, but lower agreement results in reduced utility for the same privacy requirements. Yet suppressing diversity to artificially increase agreement is undesirable, as it distorts the output of the underlying model, and thus reduces output quality.
We propose Hot PATE, a variant of PATE designed for diverse generative settings. We formalize the notion of a diversity-preserving ensemble sampler and introduce an efficient sampler that provably transfers diversity without incurring additional privacy cost. Hot PATE requires only API access to proprietary models and can be used as a drop-in replacement for existing Cold PATE samplers. Our empirical evaluations corroborate and quantify the benefits, showing significant improvements in the privacy–utility trade-off on evaluated in-context learning tasks, both in preserving diversity and in returning relevant responses.
View details
Scaling Embedding Layers in Language Models
Da Yu
Yangsibo Huang
Pritish Kamath
Daogao Liu
Chiyuan Zhang
2025
Preview abstract
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 that a single all-encompassing definition may not exist. Thus, we employ a different strategy and aim to "sandwich" the concept of reconstruction attacks by addressing two complementing questions: (i) What conditions guarantee that a given system is protected against such attacks? (ii) Under what circumstances does a given attack clearly indicate that a system is not protected? More specifically,
* We introduce a new definitional paradigm -- Narcissus Resiliency -- to formulate a security definition for protection against reconstruction attacks. This paradigm has a self-referential nature that enables it to circumvent shortcomings of previously studied notions of security. Furthermore, as a side-effect, we demonstrate that Narcissus resiliency captures as special cases multiple well-studied concepts including differential privacy and other security notions of one-way functions and encryption schemes.
* We formulate a link between reconstruction attacks and Kolmogorov complexity. This allows us to put forward a criterion for evaluating when such attacks are convincingly successful.
View details
Differentially Private Insights into AI Use
Daogao Liu
Pritish Kamath
Alexander Knop
Adam Sealfon
Da Yu
Chiyuan Zhang
Conference on Language Modeling (COLM) 2025 (2025)
Preview abstract
We introduce Urania, a novel framework for generating insights about LLM chatbot interactions with rigorous differential privacy (DP) guarantees. The framework employs a private clustering mechanism and innovative keyword extraction methods, including frequency-based, TF-IDF-based, and LLM-guided approaches. By leveraging DP tools such as clustering, partition selection, and histogram-based summarization, Urania provides end-to-end privacy protection. Our evaluation assesses lexical and semantic content preservation, pair similarity, and LLM-based metrics, benchmarking against a non-private method inspired by CLIO (Tamkin et al., 2024). Moreover, we develop a simple empirical privacy evaluation that demonstrates the enhanced robustness of our DP pipeline. The results show the framework’s ability to extract meaningful conversational insights while maintaining stringent user privacy, effectively balancing data utility with privacy preservation.
View details
Preview abstract
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 these sketches can fail under adaptively chosen queries, breaking down after approximately $\tilde{O}(k^2)$ queries, where $k$ is the sketch size. In this work, we overcome this quadratic barrier by designing robust estimators with fine-grained guarantees. Specifically, our constructions can handle an exponential number of adaptive queries, provided that each element participates in at most $\tilde{O}(k^2)$ queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries sharing the same element, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.
View details
