Anders Aamand

ICML Conference 2025 Conference Paper

Breaking the n1. 5 Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition

• Anders Aamand
• Justin Y. Chen
• Mina Dalirrooyfard
• Slobodan Mitrovic
• Yuriy Nevmyvaka
• Sandeep Silwal
• Yinzhan Xu

We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $\widetilde{O}(n^{1. 5})$ additive error and $1+\gamma$ multiplicative error for any $\gamma > 0$ [Gupta, Roth, Ullman TCC’12]. In contrast, inefficient algorithms, i. e. , those requiring exponential time, can achieve an $\widetilde{O}(n)$ additive error and $1+\gamma$ multiplicative error [Eliáš, Kapralov, Kulkarni, Lee SODA’20]. In this work, we break the $n^{1. 5}$ additive error barrier for private and efficient cut sparsification. We present an $(\varepsilon, \delta)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+\gamma$ and additive error $n^{1. 25 + o(1)}$ (ignoring dependencies on $\varepsilon, \delta, \gamma$). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.

NeurIPS Conference 2025 Conference Paper

Differentially Private Gomory-Hu Trees

• Anders Aamand
• Justin Chen
• Mina Dalirrooyfard
• Slobodan Mitrovic
• Yuriy Nevmyvaka
• Sandeep Silwal
• Yinzhan Xu

Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ that preserves the Min-$s$-$t$-Cut between any pair of vertices $s, t \in V$. Finding cuts in graphs is a key primitive in problems such as bipartite matching, spectral and correlation clustering, and community detection. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s, t \in V$ with high probability. Our error bound is essentially optimal, since [Dalirrooyfard, Mitrovic and Nevmyvaka, Neurips 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $\Omega(n)$ additive error even with $(\varepsilon, \delta)$-DP and allowing for multiplicative error. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth, Ullman, TCC 2009] and $\tilde{O}(\sqrt{mn}/ \varepsilon)$ for $(\varepsilon, \delta)$-DP [Liu, Upadhyay and Zou, SODA 2024], both achieved by DP algorithms that preserve all cuts in the graph. To achieve our result, we develop an $\varepsilon$-DP algorithm for the Minimum Isolating Cuts problem with near-linear error, and introduce a novel privacy composition technique combining elements of both parallel and basic composition to handle `bounded overlap' computational branches in recursive algorithms, which maybe of independent interest.

NeurIPS Conference 2025 Conference Paper

Differentially Private Quantiles with Smaller Error

• Jacob Imola
• Fabrizio Boninsegna
• Hannah Keller
• Anders Aamand
• Amrita Roy Chowdhury
• Rasmus Pagh

In the approximate quantiles problem, the goal is to output $m$ quantile estimates, the ranks of which are as close as possible to $m$ given quantiles $0 \leq q_1 \leq\dots \leq q_m \leq 1$. We present a mechanism for approximate quantiles that satisfies $\varepsilon$-differential privacy for a dataset of $n$ real numbers where the ratio between the distance between the closest pair of points and the size of the domain is bounded by $\psi$. As long as the minimum gap between quantiles is sufficiently large, $|q_i-q_{i-1}|\geq \Omega\left(\frac{m\log(m)\log(\psi)}{n\varepsilon}\right)$ for all $i$, the maximum rank error of our mechanism is $O\left(\frac{\log(\psi) + \log^2(m)}{\varepsilon}\right)$ with high probability. Previously, the best known algorithm under pure DP was due to Kaplan, Schnapp, and Stemmer (ICML '22), who achieved a bound of $O\left(\frac{\log(\psi)\log^2(m) + \log^3(m)}{\varepsilon}\right)$. Our improvement stems from the use of continual counting techniques which allows the quantiles to be randomized in a correlated manner. We also present an $(\varepsilon, \delta)$-differentially private mechanism that relaxes the gap assumption without affecting the error bound, improving on existing methods when $\delta$ is sufficiently close to zero. We provide experimental evaluation which confirms that our mechanism performs favorably compared to prior work in practice, in particular when the number of quantiles $m$ is large.

ICML Conference 2025 Conference Paper

Improved Approximations for Hard Graph Problems using Predictions

• Anders Aamand
• Justin Y. Chen
• Siddharth Gollapudi
• Sandeep Silwal
• Hao Wu 0057

We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e. g. , learned from past data). Our prediction model builds upon and extends the $\varepsilon$-prediction framework by Cohen-Addad, d’Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024). We consider an edge-based version of this model, where each edge provides two bits of information, corresponding to predictions about whether each of its endpoints belong to an optimal solution. Even with weak predictions where each bit is only $\varepsilon$-correlated with the true solution, this information allows us to break approximation barriers in the standard setting. We develop algorithms with improved approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Independent Set problems (among others). Across these problems, our algorithms share a unifying theme, where we separately satisfy constraints related to high degree vertices (using predictions) and low-degree vertices (without using predictions) and carefully combine the answers.

ICLR Conference 2025 Conference Paper

Learning-Augmented Frequent Directions

• Anders Aamand
• Justin Y. Chen
• Siddharth Gollapudi
• Sandeep Silwal
• Hao Wu 0057

An influential paper of Hsu et al. (ICLR'19) introduced the study of learning-augmented streaming algorithms in the context of frequency estimation. A fundamental problem in the streaming literature, the goal of frequency estimation is to approximate the number of occurrences of items appearing in a long stream of data using only a small amount of memory. Hsu et al. develop a natural framework to combine the worst-case guarantees of popular solutions such as CountMin and CountSketch with learned predictions of high frequency elements. They demonstrate that learning the underlying structure of data can be used to yield better streaming algorithms, both in theory and practice. We simplify and generalize past work on learning-augmented frequency estimation. Our first contribution is a learning-augmented variant of the Misra-Gries algorithm which improves upon the error of learned CountMin and learned CountSketch and achieves the state-of-the-art performance of randomized algorithms (Aamand et al., NeurIPS'23) with a simpler, deterministic algorithm. Our second contribution is to adapt learning-augmentation to a high-dimensional generalization of frequency estimation corresponding to finding important directions (top singular vectors) of a matrix given its rows one-by-one in a stream. We analyze a learning-augmented variant of the Frequent Directions algorithm, extending the theoretical and empirical understanding of learned predictions to matrix streaming.

ICML Conference 2025 Conference Paper

Lightweight Protocols for Distributed Private Quantile Estimation

• Anders Aamand
• Fabrizio Boninsegna
• Abigail Gentle
• Jacob Imola
• Rasmus Pagh

Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We consider two adaptive algorithms for estimating one quantile (e. g. the median) when each user holds a single data point lying in a domain $[B]$ that can be queried once through a private mechanism; one under local differential privacy (LDP) and another for shuffle differential privacy (shuffle-DP). In the adaptive setting we present an $\varepsilon$-LDP algorithm which can estimate any quantile within error $\alpha$ only requiring $O(\frac{\log B}{\varepsilon^2\alpha^2})$ users, and an $(\varepsilon, \delta)$-shuffle DP algorithm requiring only $\widetilde{O}((\frac{1}{\varepsilon^2}+\frac{1}{\alpha^2})\log B)$ users. Prior (nonadaptive) algorithms require more users by several logarithmic factors in $B$. We further provide a matching lower bound for adaptive protocols, showing that our LDP algorithm is optimal in the low-$\varepsilon$ regime. Additionally, we establish lower bounds against non-adaptive protocols which paired with our understanding of the adaptive case, proves a fundamental separation between these models.

NeurIPS Conference 2024 Conference Paper

Statistical-Computational Trade-offs for Density Estimation

• Anders Aamand
• Alexandr Andoni
• Justin Y. Chen
• Piotr Indyk
• Shyam Narayanan
• Sandeep Silwal
• Haike Xu

We study the density estimation problem defined as follows: given $k$ distributions $p_1, \ldots, p_k$ over a discrete domain $[n]$, as well as a collection of samples chosen from a "query" distribution $q$ over $[n]$, output $p_i$ that is "close" to $q$. Recently Aamand et al. gave the first and only known result that achieves sublinear bounds in both the sampling complexity and the query time while preserving polynomial data structure space. However, their improvement over linear samples and time is only by subpolynomial factors. Our main result is a lower bound showing that, for a broad class of data structures, their bounds cannot be significantly improved. In particular, if an algorithm uses $O(n/\log^c k)$ samples for some constant $c>0$ and polynomial space, then the query time of the data structure must be at least $k^{1-O(1)/\log \log k}$, i. e. , close to linear in the number of distributions $k$. This is a novel statistical-computational trade-off for density estimation, demonstrating that any data structure must use close to a linear number of samples or take close to linear query time. The lower bound holds even in the realizable case where $q=p_i$ for some $i$, and when the distributions are flat (specifically, all distributions are uniform over half of the domain $[n]$). We also give a simple data structure for our lower bound instance with asymptotically matching upper bounds. Experiments show that the data structure is quite efficient in practice.

NeurIPS Conference 2023 Conference Paper

Constant Approximation for Individual Preference Stable Clustering

• Anders Aamand
• Justin Chen
• Allen Liu
• Sandeep Silwal
• Pattara Sukprasert
• Ali Vakilian
• Fred Zhang

Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is $\alpha$-IP stable if the average distance of every data point to its own cluster is at most $\alpha$ times the average distance to any other cluster. Unfortunately, determining if a dataset admits a $1$-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown if an $o(n)$-IP stable clustering always exists, as the prior state of the art only guaranteed an $O(n)$-IP stable clustering. We close this gap in understanding and show that an $O(1)$-IP stable clustering always exists for general metrics, and we give an efficient algorithm which outputs such a clustering. We also introduce generalizations of IP stability beyond average distance and give efficient near optimal algorithms in the cases where we consider the maximum and minimum distances within and between clusters.

ICML Conference 2023 Conference Paper

Data Structures for Density Estimation

• Anders Aamand
• Alexandr Andoni
• Justin Y. Chen
• Piotr Indyk
• Shyam Narayanan
• Sandeep Silwal

We study statistical/computational tradeoffs for the following density estimation problem: given $k$ distributions $v_1, \ldots, v_k$ over a discrete domain of size $n$, and sampling access to a distribution $p$, identify $v_i$ that is "close" to $p$. Our main result is the first data structure that, given a sublinear (in $n$) number of samples from $p$, identifies $v_i$ in time sublinear in $k$. We also give an improved version of the algorithm of Acharya et al. (2018) that reports $v_i$ in time linear in $k$. The experimental evaluation of the latter algorithm shows that it achieves a significant reduction in the number of operations needed to achieve a given accuracy compared to prior work.

NeurIPS Conference 2023 Conference Paper

Improved Frequency Estimation Algorithms with and without Predictions

• Anders Aamand
• Justin Chen
• Huy Nguyen
• Sandeep Silwal
• Ali Vakilian

Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e. g. , CountMin and CountSketch) come with worst-case guarantees that probabilistically bound the error of the estimated frequencies for any possible input. The work of Hsu et al. ~(2019) introduced the idea of using machine learning to tailor sketching algorithms to the specific data distribution they are being run on. In particular, their learning-augmented frequency estimation algorithm uses a learned heavy-hitter oracle which predicts which elements will appear many times in the stream. We give a novel algorithm, which in some parameter regimes, already theoretically outperforms the learning based algorithm of Hsu et al. without the use of any predictions. Augmenting our algorithm with heavy-hitter predictions further reduces the error and improves upon the state of the art. Empirically, our algorithms achieve superior performance in all experiments compared to prior approaches.

SODA Conference 2023 Conference Paper

Online Sorting and Translational Packing of Convex Polygons

• Anders Aamand
• Mikkel Abrahamsen
• Lorenzo Beretta 0001
• Linda Kleist

We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used space. Among other variants, we consider strip packing and bin packing, where the container is the infinite horizontal strip [0, ∞) × [0, 1] or a collection of 1 × 1 bins, respectively. If polygons may be rotated, there exist O (1)-competitive online algorithms for all problems at hand [Baker and Schwarz, SIAM J. Comput. , 1983]. Likewise, if the polygons may not be rotated but only translated, then using a result from [Alt, de Berg and Knauer, JoCG, 2017] we can derive O (1)-approximation algorithms for all problems at hand. Thus, it is natural to conjecture that the online version of these problems, in which only translations are allowed, also admits a O (1)-competitive algorithm. We disprove this conjecture by showing a superconstant lower bound on the competitive ratio for several online packing problems. The offline approximation algorithm for translation-only packing sorts the convex polygons by their “natural slope”, so that they form a fan-like pattern. We prove that this step is essential, in the sense that packing polygons without rotating them is as hard as sorting numbers online. Technically, we prove lower bounds on the competitive ratio of translation-only online packing problems by reducing from a purpose-built novel and natural combinatorial problem that we call online sorting. In a nutshell, the problem requires us to place n numbers x 1, …, x n coming online into an oversized array of length γ n for γ ≥ 1, while minimizing the sum of absolute differences of consecutive numbers. Note that the offline optimum is achieved by sorting x 1, …, x n. We show a superconstant lower bound on the competitive ratio of online sorting, for any constant γ. We prove that this yields superconstant lower bounds for all packing problems at hand. We believe that this technique is of independent interest since it uncovers a deep connection between inherently geometrical and purely combinatorial problems. As a complement, we also include algorithms for both online sorting and translation-only online strip packing with non-trivial competitive ratios. Our algorithm for strip packing relies on a new technique for recursively subdividing the strip into parallelograms of varying height, thickness and slope.

NeurIPS Conference 2022 Conference Paper

(Optimal) Online Bipartite Matching with Degree Information

• Anders Aamand
• Justin Chen
• Piotr Indyk

We propose a model for online graph problems where algorithms are given access to an oracle that predicts (e. g. , based on modeling assumptions or past data) the degrees of nodes in the graph. Within this model, we study the classic problem of online bipartite matching, and a natural greedy matching algorithm called MinPredictedDegree, which uses predictions of the degrees of offline nodes. For the bipartite version of a stochastic graph model due to Chung, Lu, and Vu where the expected values of the offline degrees are known and used as predictions, we show that MinPredictedDegree stochastically dominates any other online algorithm, i. e. , it is optimal for graphs drawn from this model. Since the "symmetric" version of the model, where all online nodes are identical, is a special case of the well-studied "known i. i. d. model", it follows that the competitive ratio of MinPredictedDegree on such inputs is at least 0. 7299. For the special case of graphs with power law degree distributions, we show that MinPredictedDegree frequently produces matchings almost as large as the true maximum matching on such graphs. We complement these results with an extensive empirical evaluation showing that MinPredictedDegree compares favorably to state-of-the-art online algorithms for online matching.

NeurIPS Conference 2022 Conference Paper

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks

• Anders Aamand
• Justin Chen
• Piotr Indyk
• Shyam Narayanan
• Ronitt Rubinfeld
• Nicholas Schiefer
• Sandeep Silwal
• Tal Wagner

Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the “combine” function of size polynomial or even exponential in the number of graph nodes $n$, as well as feature vectors of length linear in $n$. We present an improved simulation of the WL test on GNNs with {\em exponentially} lower complexity. In particular, the neural network implementing the combine function in each node has only $\mathrm{polylog}(n)$ parameters, and the feature vectors exchanged by the nodes of GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.

STOC Conference 2021 Conference Paper

Load balancing with dynamic set of balls and bins

• Anders Aamand
• Jakob Bæk Tejs Knudsen
• Mikkel Thorup

STOC Conference 2020 Conference Paper

Fast hashing with strong concentration bounds

• Anders Aamand
• Jakob Bæk Tejs Knudsen
• Mathias Bæk Tejs Knudsen
• Peter Michael Reichstein Rasmussen
• Mikkel Thorup

Previous work on tabulation hashing by Pǎtraşcu and Thorup from STOC’11 on simple tabulation and from SODA’13 on twisted tabulation offered Chernoff-style concentration bounds on hash based sums, e.g., the number of balls/keys hashing to a given bin, but under some quite severe restrictions on the expected values of these sums. The basic idea in tabulation hashing is to view a key as consisting of c = O (1) characters, e.g., a 64-bit key as c =8 characters of 8-bits. The character domain Σ should be small enough that character tables of size |Σ| fit in fast cache. The schemes then use O (1) tables of this size, so the space of tabulation hashing is O (|Σ|). However, the concentration bounds by Pǎtraşcu and Thorup only apply if the expected sums are ≪ |Σ|.

SODA Conference 2019 Conference Paper

Non-empty Bins with Simple Tabulation Hashing

• Anders Aamand
• Mikkel Thorup

We consider the hashing of a set X ⊆ U with | X | = m using a simple tabulation hash function h: U → [ n ] = {0, …, n – 1} and analyse the number of non-empty bins, that is, the size of h ( X ). We show that the expected size of h ( X ) matches that with fully random hashing to within low-order terms. We also provide concentration bounds. The number of non-empty bins is a fundamental measure in the balls and bins paradigm, and it is critical in applications such as Bloom filters and Filter hashing. For example, normally Bloom filters are proportioned for a desired low false-positive probability assuming fully random hashing. Our results imply that if we implement the hashing with simple tabulation, we obtain the same low false-positive probability for any possible input.