Minimizing Recourse in an Adaptive Balls and Bins Game

Fine, Adi; Kaplan, Haim; Stemmer, Uri

doi:10.4230/LIPIcs.ICALP.2025.77

Minimizing Recourse in an Adaptive Balls and Bins Game

Adi Fine Blavatnik School of Computer Science, Tel Aviv University, Israel Haim Kaplan

Blavatnik School of Computer Science, Tel Aviv University, Israel Uri Stemmer

Blavatnik School of Computer Science, Tel Aviv University, Israel

Abstract

We consider a simple load-balancing game between an algorithm and an adaptive adversary. In a simplified version of this game, the adversary observes the assignment of jobs to machines and selects a machine to kill. The algorithm must then restart the jobs from the failed machine on other machines. The adversary repeats this process, observing the new assignment and eliminating another machine, and so on. The adversary aims to force the algorithm to perform many restarts, while we seek a robust algorithm that minimizes restarts regardless of the adversary’s strategy. This game was recently introduced by Bhattacharya et al. for designing a $3$ -spanner with low recourse against an adaptive adversary.

We prove that a simple algorithm, which assigns each job to a randomly chosen live bin, incurs $O(n\log n)$ recourse against an adaptive adversary. This enables us to construct a much simpler $3$ -spanner with a recourse that is smaller by a factor of $O(\log^{2}n)$ compared to the previous construction, without increasing the update time or the size of the spanner.

This motivates a careful examination of the range of attacks an adaptive adversary can deploy against simple algorithms before resorting to more complex ones. As our case study demonstrates, this attack space may not be as large as it initially appears, enabling the development of robust algorithms that are both simpler and easier to analyze.

Keywords and phrases:

Adaptive adversary, load-balancing game, balls-and-bins, randomized algorithms, dynamic 3-spanner, dynamic graph algorithms, adversarial robustness

Category:

Track A: Algorithms, Complexity and Games

Funding:

Adi Fine: This work was partially supported by the Israel Science Foundation grant no. 1156/23 and the Blavatnik Family Foundation.

Haim Kaplan: This work was partially supported by the Israel Science Foundation grant no. 1156/23 and the Blavatnik Family Foundation.

Uri Stemmer: This work was partially supported by the Israel Science Foundation grant 1419/24 and the Blavatnik Family Foundation.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Adversary models ; Theory of computation

\rightarrow

Sparsification and spanners ; Theory of computation

\rightarrow

Dynamic graph algorithms

DOI:

10.4230/LIPIcs.ICALP.2025.77

Event:

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Editors:

Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Real-world systems rarely operate in isolation – rather, they respond to sequences of updates that may themselves be influenced by prior feedback from the system itself. This phenomenon is particularly concerning in adversarial settings, where an adversary interacts with the system to select inputs adaptively in order to exploit its weaknesses, or force worst-case behavior.

This motivates us to analyze the worst case performance of algorithms that get their input via an interaction with an adaptive environment (or adversary). This adversary responds to prior outputs of the algorithm and may be malicious. Such an analysis may be needed for streaming and dynamic graph algorithms [11, 45, 57, 23, 28, 43, 56] and for online learning and machine unlearning models [42, 30, 33]. The importance of adaptivity has grown in recent years, particularly with the rise of feedback loops in machine learning and data analysis, since when the algorithm takes inputs that depend on its prior outputs we risk overfitting and biased results.

If the algorithm is deterministic, then analyzing it against an adaptive input is equivalent to analyzing it against an oblivious input (which means that the sequence of interactions with the algorithm is fixed ahead of time). The reason is that the adversary cannot gain any information about the algorithm that it did not have before it interacts with it (we assume that the algorithm is public). However, if the algorithm is randomized, then the adversary may reveal via feedback that the algorithm provides information about the algorithm’s random coins. Then it can use this information to cause the algorithm to perform poorly.

A major obstacle in tackling adaptivity is the lack of applicable analytical tools. Many classical probabilistic techniques, such as various concentration bounds require independence or martingale assumptions on the random variables, that often could not be guaranteed in an adaptive interaction. Furthermore, even the length and purpose of the sequence of random coins that the algorithm uses, depends on the actions of the adversary, and are not fixed before the interaction starts. All this often makes the analysis of the worst case against an adaptive adversary quite challenging.

The holy grail to circumvent all these difficulties is to find a deterministic algorithm (which cannot be fooled as we argued before). Indeed, this has been shown to be achievable for several problems of interest [52, 18, 19, 46, 16, 8]. However, there are many cases for which deterministic algorithms do not exist or remain elusive. Maybe the simplest example is the classical adaptive data analysis problem [34, 44]. Here we want to estimate the probability in the population of each predicate in a sequence of predicates chosen adaptively: The next predicate is chosen based on the estimations returned by the algorithm for the previous ones. The data available to us for this estimation task is a sample of the population, so the analysis is inherently randomized. The risk is that the adversary will be able to find predicates that overfit the sample (i.e. their frequency in the sample is very different than their frequency in the population). In this context, techniques have been developed to guarantee that such overfitting does not happen if we do not allow the adversary to estimate too many predicates [34, 6, 54, 50, 21].

Same problem exists in many streaming tasks such estimating the heavy hitters [26, 32] or estimating the second moment [2]. To perform these tasks without consuming too much space randomization must be used [49, 2]. Therefore, if the input sequence depends on intermediate estimates returned by the algorithm (such as occasional reports of the heavy hitters), then standard analysis collapse and we risk an adversary that exploits these estimates and finds a sequence on which the error of the algorithm is large. Recently, streaming algorithms have been developed to prevent the adversary from finding short sequences that fool the algorithm [11, 45, 57, 31, 3, 10, 1]. Similar examples from the field of dynamic algorithms include [29, 43, 56, 15]. In particular, the proactive sampling technique [15] was developed to construct dynamic cut sparsifiers that remain effective against an adaptive adversary. These special “protection” techniques against an adaptive adversary are often difficult to deploy and analyze, and they frequently incur large time and space overhead.

In these examples there is some input (sometimes even with probability $1$ over the randomness of the algorithm) on which the algorithm has large error, but the algorithm is designed such that the adversary needs a rather long interaction in order to find it. In contrast, there may be situations in which there is no strategy for the adversary, that can fool a simple algorithm that is provable good in an oblivious setting. Identifying such scenarios in which the adversary, despite its seemingly large control, is inherently powerless is important. In such situations, we may be safe using a simple algorithm rather than wasting time and space on “protection” mechanisms that are not needed.

Our results

(1) Load balancing Games.

We consider a family of simple games between an algorithm and an adversary that seems powerful. We prove that in fact this seemingly strong adversary has no way to fool the most natural algorithm. These games generalize load balancing games that were introduced by [20] in order to design a 3-spanner with small recourse against an adaptive adversary (more on spanner with small recourse below). In [20] they designed an algorithm based on a version of the proactive sampling technique for this load balancing game and thereby obtained an efficient 3-spanner algorithm against an adaptive adversary. Their algorithm proactively refreshes its random bits in order to hide them from the adversary and its analysis is somewhat challenging.

Our analysis shows that, in fact, a simple algorithm for this game cannot be fooled by an adaptive adversary. Specifically, we prove that the adversary has no winning strategy against this algorithm, so there is no reason for the algorithm to hide its randomness. A key lesson from our proof is that one should first carefully analyze the actual power of an adaptive adversary against simple strategies that succeed in the oblivious setting, before resorting to complex algorithms that may be unnecessary for protection against adaptive attacks or dangerous feedback loops.

A simplified version of this load balancing game is best described in the classical balls and bins framework. We have $n$ balls and $n$ bins. The adversary looks at our assignment (it sees exactly how many balls we have in each bin) and picks a bin to delete. We have to take the balls in this bin and redistribute them in the remaining bins. The game continues this way until one bin remains with all balls in it. The goal of the adversary is to maximize the sum of the numbers of balls in the deleted bins (at the moment when they are deleted). In other words, it wants to maximize the total number of balls that we redistribute. We also use the term recourse for this quantity, as it represents the total number of changes in the data structure. The goal is to find a simple algorithm for which the adaptive adversary cannot cause high recourse.

A simple strategy is to pick a new bin randomly among the remaining bins for each ball in the deleted bin. We prove that this scheme has $O(n\log n)$ recourse with high probability. Moreover, this bound is asymptotically tight, as no strategy can achieve better recourse: A deterministic greedy adversary that always deletes the bin with maximum load ensures that each deletion contributes at least the average load among the remaining bins, leading to recourse of at least $\sum_{j=n}^{1}{\frac{n}{j}}=\Omega(n\log{n})$ .

Our proof technique is quite simple: using stochastic domination and a basic concentration bound for a sum of geometric random variables, we prove that the probability of failing against a fixed deletion ordering is so small that it remains small even after applying a union bound over all possible deletion orderings. We then generalize this proof to more complicated load balancing games, where each ball has a different probability distribution over the bins, and we use this distribution each time we redraw a bin for it. Additionally, we extend the proof to a setting in which the graph is actually a hypergraph, where a ball can be simultaneously in several bins. In this case, we need to redraw the bins when one of the bins containing the ball is eliminated.

We can imagine several natural applications for this game, such as managing a server farm. When a server goes down (for any reason), we need to redistribute and restart the jobs running on it among the remaining servers. These restarts are expensive, so we want to redistribute the jobs in a way that minimizes the number of restarts. This is especially important if a malicious, adaptive adversary is attacking our farm, causing servers to go down one by one.

(2) $3$ -spanner with small recourse.

Another application of our improved analysis of the load balancing game described above is the construction of a $3$ -spanner with better performance against an adaptive adversary.

Prior to the work of [20] the only known dynamic spanner algorithm against an adaptive adversary required $O(n)$ amortized update time to maintain a $(2k-1)$ -spanner of size $O(n^{1+1/k})$ and this only for $k\leq 3$ . Only for large stretch of $k=\log^{6}(n)$ a construction with polylogarithmic update time was recently discovered [15]. This in contrast to the oblivious setting where we know how to maintain a $(2k-1)$ -spanner of size $O(n^{1+1/k})$ for any $k\geq 1$ in $O(k\log^{2}n)$ amortized update time (and slightly larger but polylogarithmic worst case update time). As noted by [20], even if we allow infinite time and only count recourse (which is the number of changes in the dynamic data structure per update), no data structure with sublinear recourse was known for small $k$ . So naturally [20] asked whether we can construct a spanner with small recourse for small value of $k$ . Beside being a prerequisite for small update time, recourse is an important metric in dynamic algorithms in general. It is particularly important in settings where modifying the solution is costly, even when computation itself is inexpensive [40, 39, 5, 41]. Furthermore, low recourse has historically been a stepping stone to achieve faster dynamic algorithms in fundamental problems such as Matching, Single source shortest path, Set cover and more [48, 47, 25, 9, 27, 41, 51, 17].

Bhattacharya et al. [20] answered their question positively and presented several constructions for spanners with low recourse against an adaptive adversary. For $3$ -spanner, their construction also had a small update time of $O(\sqrt{n}\log n)$ simultaneously with polylogarithmic recourse. To achieve this, they used a rather involved algorithm that employs proactive sampling. Our analysis of the load balancing game described above allows us to obtain a simpler algorithm (with a simpler analysis) for the $3$ -spanner against an adaptive adversary, with improved performance. Specifically, our algorithm maintains a fully dynamic 3-spanner of size $O(n\sqrt{n})$ , with $O(\log n)$ amortized recourse per operation with high probability and $O(\sqrt{n}\log{n})$ worst-case update time. This improves the recourse bound of [20] by a $\log^{2}{n}$ factor.

Additional games and related questions

For the load balancing game, one can consider other simple algorithms in which the balls are not distributed independently and randomly. For example, we can imagine situations where we want to redistribute the balls in bunches into a relatively small number of bins. This approach may be more communication-efficient in the server farm application described earlier. However, the dependencies introduced by such strategies between the balls make them even more challenging to analyze. We elaborate on this in Section 5.

There are even simpler scenarios where adaptivity is an issue and presents an analytical challenge. The analysis tools developed for these scenarios may be useful for analyzing more complicated games. In these simple scenarios, we aim to understand the worst-case behavior of a fixed strategy against a specific adaptive method of generating its input sequence. One classical example is Polya’s urm model [35, 53]. Another example is the Optimal Ball Recycling problem studied by Bender et al. [12]. In this game, an adversary picks a set of balls in a bin (or another well-defined subset of the balls) and redistributes them (the bin is not removed) according to a fixed probability distribution over the bins, which is the same for all balls. They studied the steady-state distribution of several adaptive strategies, such as redistributing the balls in the fullest bin, using techniques from the theory of Markov Decision Processes.

The structure of the paper is as follows: In section 2 we describe a simple version of our load balancing framework as a warm-up. This version already demonstrates the main ideas in our analysis. We generalize this framework in Section 3. In Section 4 we describe our improves spanner construction. We conclude in Section 5.

2 Balls and Bins, Deletion Against An Adaptive Adversary

In this game, we have $\mathop{\textnormal{N}}\nolimits$ bins and $\mathop{\textnormal{N}}\nolimits$ identical balls. Additionally, we assume that $\mathop{\textnormal{N}}\nolimits$ is a power of $2$ , i.e. $\mathop{\textnormal{N}}\nolimits=2^{z}$ for some integer $z\in\mathbb{N}$ .

Initially, the balls are distributed arbitrarily among the $\mathop{\textnormal{N}}\nolimits$ bins. Then, at each step, an adversary chooses one bin to delete. The chosen bin is removed, and all of its balls are re-thrown uniformly into the remaining bins. This process continues until only one bin remains.

We are interested in minimizing the value of a random variable which we call $R e c o u r s e$ . This variable counts the total number of balls in the bins that the adversary deletes at the moments they are deleted. This is the same as the total number of balls that the algorithm re-throws. We prove the following theorem.

Theorem 1 (Main theorem).

$Pr[Recourse>13\cdot\mathop{\textnormal{N}}\nolimits\log_{2}{\mathop{% \textnormal{N}}\nolimits}\ ]\leq\exp{\big{(}-\mathop{\textnormal{N}}\nolimits% \ln{\mathop{\textnormal{N}}\nolimits}\ \big{)}}$

We first assume that the adversary is oblivious and deletes bins in the order given by a permutation $\pi$ (that is first bin deleted is $\pi(1)$ , then $\pi(2)$ until $\pi(\mathop{\textnormal{N}}\nolimits)$ ). To simplify the presentation we also assume, without loss of generality, that $\pi$ is the identity. That is we first delete bin $1$ , then $2$ , and the last bin deleted is $\mathop{\textnormal{N}}\nolimits$ .

Let $Recourse(\pi)$ be a random value equals to the total recourse of an oblivious adversary that deletes bins according to $\pi$ . We prove the following:

Theorem 2.

$Pr[Recourse(\pi)>13\cdot\mathop{\textnormal{N}}\nolimits\log_{2}{\mathop{% \textnormal{N}}\nolimits}\,]\leq\exp{\big{(}-2\mathop{\textnormal{N}}\nolimits% \ln{\mathop{\textnormal{N}}\nolimits}\ \big{)}}$

We focus on a single ball $b$ and the recourse it incurs during its movements.

Definition 3 (Phase).

A phase is a disjoint interval of consecutive bins deletions. For an integer $\mathop{\textnormal{$\phi$}}\nolimits\in\{1,2,...,\log_{2}{\mathop{\textnormal% {N}}\nolimits}\,\}$ , define

\displaystyle q(\mathop{\textnormal{$\phi$}}\nolimits)=1+\mathop{\textnormal{N% }}\nolimits\Bigl{(}1-\frac{1}{2^{\mathop{\textnormal{$\phi$}}\nolimits-1}}% \Bigr{)}

to be the first bin deleted in phase $\mathop{\textnormal{$\phi$}}\nolimits$ .

In particular, phase $\mathop{\textnormal{$\phi$}}\nolimits$ consists of the bins deleted from $q(\mathop{\textnormal{$\phi$}}\nolimits)$ through $\,q(\mathop{\textnormal{$\phi$}}\nolimits+1)-1.$ Phase $1$ goes from bin $1$ to bin $\mathop{\textnormal{N}}\nolimits/2$ , phase $2$ goes from bin $1+\mathop{\textnormal{N}}\nolimits/2$ to bin $3\mathop{\textnormal{N}}\nolimits/4$ , and so on.

For each phase $\mathop{\textnormal{$\phi$}}\nolimits$ , we define a random variable $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ to measure the recourse of ball $b$ caused by the deletions occurring in phase $\mathop{\textnormal{$\phi$}}\nolimits$ . If ball $b$ never landed in any of phase $\mathop{\textnormal{$\phi$}}\nolimits$ ’s bins, $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)=0$ . Otherwise, it equals the number of bins that ball $b$ visited during phase $\mathop{\textnormal{$\phi$}}\nolimits$ . We show that $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ is essentially dominated by a geometric random variable. Intuitively this follows since the probability that a ball keeps re-landing in the same phase is at most $0.5$ each time.

Definition 4 (First-order stochastic dominance).

Let $X$ and $Y$ be two random variables such that

\displaystyle Pr[X>u]\leq Pr[Y>u]\text{ for all }u\in(-\infty,\infty).

Then $Y$ has first-order stochastic dominance over $X$ , and it is denoted by $X\preceq Y$ .

Let $Geo(0.5)$ be a geometric random variable with success probability $0.5$ .

Lemma 5.

$R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\preceq\big{(}1+Geo(0.5)\,\big{)}$ , i.e. $Pr\Big{[}R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)>u\Big{]}\leq Pr\Big{[}% \big{(}1+Geo(0.5)\,\big{)}>u\Big{]}$ for all $u\in(-\infty,\infty)$ .

Proof.

Both $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ and $Geo(0.5)$ can only receive integer values, thus it is enough to prove the statement for integer values of $u$ .

Notice that $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\geq 0$ , so the claim is trivially true for $u<0$ . Also, $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ cannot exceed the total number of bins in phase $\mathop{\textnormal{$\phi$}}\nolimits$ , i.e. $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\leq\frac{\mathop{\textnormal{N}}% \nolimits}{2^{\mathop{\textnormal{$\phi$}}\nolimits}}$ , so the lemma is also trivially true for $u\geq\frac{\mathop{\textnormal{N}}\nolimits}{2^{\mathop{\textnormal{$\phi$}}% \nolimits}}$ .

We prove the bound for intermediate values of $u$ by induction on $u\in\big{[}0,\frac{\mathop{\textnormal{N}}\nolimits}{2^{\mathop{\textnormal{$% \phi$}}\nolimits}}\big{]}$ .

Base case ( $u=0$ ).

This holds trivially since $Pr\Big{[}\big{(}1+Geo(0.5)\big{)}>0\Big{]}=1$ .

Let $STAYIN(\mathop{\textnormal{$\phi$}}\nolimits,\ u-1)$ be the event that, after $u-1$ re-throws in phase $\mathop{\textnormal{$\phi$}}\nolimits$ , the ball is still in a bin of this same phase.

Inductive step.

Assume the statement holds for $u-1$ , i.e. $Pr\Big{[}R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)>u-1\Big{]}\leq Pr\Big{[}% \big{(}1+Geo(0.5)\big{)}>u-1\Big{]}$ . Then:

	$\displaystyle Pr[R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)>u]$	$\displaystyle=Pr\Big{[}R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)>u-1\,\cap% \,STAYIN(\phi,\ u-1)\,\Big{]}$
		$\displaystyle=Pr\Big{[}R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)>u-1\Big{]}% \cdot Pr\Big{[}STAYIN(\phi,\ u-1)\,\|\,R_{b}(\mathop{\textnormal{$\phi$}}% \nolimits)>u-1\,\Big{]}$
		$\displaystyle\leq Pr\Big{[}\big{(}1+Geo(0.5)\big{)}>u-1\Big{]}\cdot Pr\Big{[}% \,STAYIN(\phi,\ u-1)\,\|\,R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)>u-1\,% \Big{]}$
		$\displaystyle\leq Pr\Big{[}\big{(}1+Geo(0.5)\big{)}>u-1\Big{]}\cdot 0.5$
		$\displaystyle=Pr\Big{[}\big{(}1+Geo(0.5)\big{)}>u\Big{]}.$

The $0.5$ on the right-hand side of the second inequality follows because bins in phase $\mathop{\textnormal{$\phi$}}\nolimits$ account for less than half of the remaining bins. Thus, when the ball is re-thrown uniformly, it lands again in a phase- $\mathop{\textnormal{$\phi$}}\nolimits$ ’s bin with probability at most $0.5$ . We conclude that $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\preceq\big{(}1+Geo(0.5)\big{)}$ so the lemma follows. $\hfill\blacktriangleleft$

We need the following two technical theorems in order to bound the total recourse incurred by all $\mathop{\textnormal{N}}\nolimits$ balls for the deletion order $\pi$ and prove Theorem 2. The first says that the stochastic domination relation carries over for sums of random variables.

Theorem 6 ([55]).

Let $\{X_{k},k=1,2,\dots,m\}$ be a sequence of $m$ independent random variables. Let $\{Y_{k},k=1,2,\dots,m\}$ be another sequence of $m$ independent random variables.
If $X_{k}\preceq Y_{k}$ for $k=1,2,...,m$ , then:

\displaystyle\sum_{k=1}^{m}X_{k}\ \preceq\ \sum_{k=1}^{m}Y_{k}.

The second theorem is a concentration bound for the sum of geometric random variables.

Theorem 7 ([24]).

Let $GS(n,p)$ be a negative binomially distributed random variable which is the sum of $n$ i.i.d. geometrically distributed random variables, each with success probability $p$ . Then, for $k>1$ :

\displaystyle Pr\Big{[}GS(n,p)>\frac{k\cdot n}{p}\,\Big{]}\leq\exp{\Bigl{(}-% \frac{k(1-1/k)^{2}}{2}\cdot n\Bigr{)}}.

Proof of Theorem 2.

Observe that all variables $R_{i}(\mathop{\textnormal{$\phi$}}\nolimits)$ are independent, the recourse of a single ball does not affect the recourse of other balls, and a ball’s recourse in one phase does not affect its recourse in another phase. Thus, we can apply Theorem 6 along with Lemma 5.

By Lemma 5, for each ball $i$ and phase $\mathop{\textnormal{$\phi$}}\nolimits$ , $R_{i}(\mathop{\textnormal{$\phi$}}\nolimits)\preceq\big{(}1+Geo(0.5)\big{)}$ .

Let $\mathop{\textnormal{$\Phi$}}\nolimits=\log_{2}{\mathop{\textnormal{N}}\nolimits}$ , the index of the final phase. Note that all phases, from phase $1$ to phase $\mathop{\textnormal{$\Phi$}}\nolimits$ , include all bins except the last. Therefore, by Theorem 6:

	$\displaystyle Recourse(\pi)$	$\displaystyle=\sum_{i=1}^{\mathop{\textnormal{N}}\nolimits}\,\sum_{\mathop{% \textnormal{$\phi$}}\nolimits=1}^{\mathop{\textnormal{$\Phi$}}\nolimits}R_{i}(% \mathop{\textnormal{$\phi$}}\nolimits)\preceq\sum_{i=1}^{\mathop{\textnormal{N% }}\nolimits}\,\sum_{\mathop{\textnormal{$\phi$}}\nolimits=1}^{\mathop{% \textnormal{$\Phi$}}\nolimits}\Big{(}1+Geo(0.5)\Big{)}$
		$\displaystyle=\mathop{\textnormal{N}}\nolimits\cdot\mathop{\textnormal{$\Phi$}% }\nolimits+GS\Big{(}\mathop{\textnormal{N}}\nolimits\cdot\mathop{\textnormal{$% \Phi$}}\nolimits,\,0.5\Big{)}=\mathop{\textnormal{N}}\nolimits\cdot\log_{2}{% \mathop{\textnormal{N}}\nolimits}+GS\Big{(}\mathop{\textnormal{N}}\nolimits% \cdot\log_{2}{\mathop{\textnormal{N}}\nolimits},\,0.5\Big{)}.$

Using Theorem 7 with $k=6$ to bound the sum of these $\mathop{\textnormal{N}}\nolimits\log_{2}{\mathop{\textnormal{N}}\nolimits}$ geometric random variables, we get

	$\displaystyle Pr\Big{[}Recourse(\pi)>13\cdot\mathop{\textnormal{N}}\nolimits% \cdot\log_{2}{\mathop{\textnormal{N}}\nolimits}\,\Big{]}$	$\displaystyle\leq Pr\Big{[}\mathop{\textnormal{N}}\nolimits\cdot\log_{2}{% \mathop{\textnormal{N}}\nolimits}+GS\Big{(}\mathop{\textnormal{N}}\nolimits% \cdot\log_{2}{\mathop{\textnormal{N}}\nolimits},\,0.5\Big{)}>13\cdot\mathop{% \textnormal{N}}\nolimits\cdot\log_{2}{\mathop{\textnormal{N}}\nolimits}\ \Big{]}$
		$\displaystyle=Pr\Big{[}GS\Big{(}\mathop{\textnormal{N}}\nolimits\cdot\log_{2}{% \mathop{\textnormal{N}}\nolimits},\,0.5\Big{)}>\frac{6\cdot\mathop{\textnormal% {N}}\nolimits\cdot\log_{2}{\mathop{\textnormal{N}}\nolimits}}{0.5}\ \Big{]}$
		$\displaystyle\leq\exp{\Big{(}-\frac{6(1-1/6)^{2}}{2}\mathop{\textnormal{N}}% \nolimits\cdot\log_{2}{\mathop{\textnormal{N}}\nolimits}\ \Big{)}}\leq\exp{% \big{(}-2\mathop{\textnormal{N}}\nolimits\ln{\mathop{\textnormal{N}}\nolimits}% \ \big{)}},$

so the theorem follows. $\hfill\blacktriangleleft$

We now prove our main theorem:

Proof of Theorem 1.

We model a simultaneous game against all possible choices of the adaptive adversary using a rooted game tree $T$ . Each node in $T$ represents an assignment of the balls into the bins which have not yet been deleted. The root represents the initial assignment of the balls into $\mathop{\textnormal{N}}\nolimits$ bins. A node $v$ which has $\ell$ remaining bins (at depth $\mathop{\textnormal{N}}\nolimits-\ell$ of $T$ ) has $\ell$ children, each corresponds to a possible decision of the adversary (delete the first among remaining bins, the second, etc). Each edge from $v$ to a child $u$ is associated with sufficiently many random bits to redistribute the balls in the bin which the adversary deletes when it faces the configuration associated with $v$ . Each leaf corresponds to a configuration with a single bin containing all the balls. The tree has a total of $\mathop{\textnormal{N}}\nolimits!$ distinct leaves at depth $\mathop{\textnormal{N}}\nolimits$ . The path from the root to a leaf corresponds to a permutation $\pi$ which represents a complete deletion order of the bins.

The probability space of this simultaneous game corresponds to union of the random bits on all the edges of $T$ . Once we flip all these bits then the simultaneous game is completely determined and in particular the recourse associated with each leaf (deletion ordering) is determined.

Theorem 2 bounds the probability that the recourse is high at a specific leaf. We use the union bound to bound the probability that the recourse is high in at least one leaf as follows

	$\displaystyle Pr\bigl{[}\text{There is an order of deletion with recourse % greater than }13\cdot\mathop{\textnormal{N}}\nolimits\log_{2}{\mathop{% \textnormal{N}}\nolimits}\ \bigr{]}$
	$\displaystyle\leq\mathop{\textnormal{N}}\nolimits!\cdot\exp{\bigl{(}-2\mathop{% \textnormal{N}}\nolimits\ln{\mathop{\textnormal{N}}\nolimits}\,\bigr{)}}\leq% \exp{\bigl{(}\,\mathop{\textnormal{N}}\nolimits\ln{\mathop{\textnormal{N}}% \nolimits}-2\mathop{\textnormal{N}}\nolimits\ln{\mathop{\textnormal{N}}% \nolimits}\,\bigr{)}}=\exp{\bigl{(}-\mathop{\textnormal{N}}\nolimits\ln{% \mathop{\textnormal{N}}\nolimits}\,\bigr{)}}.$

Clearly if the recourse is small in every leaf then the adversary cannot cause the algorithm to have an high recourse so the theorem follows. $\hfill\blacktriangleleft$

3 Decremental Load Balancing Framework

We consider the following setting. We have a bipartite hyper-graph consisting of $\mathop{\textnormal{M}}\nolimits$ jobs on one side and $\mathop{\textnormal{N}}\nolimits\geq 2$ machines on the other. The two sides are connected by hyper-edges, where each hyper-edge connects a single job to a nonempty subset of machines. We have to maintain a valid covering of the jobs, i.e. every job that connects to some hyper-edges must be covered by exactly one hyper-edge. The jobs are not identical; each job $i$ has its own probability distribution over the hyper-edges that contain it. Let $p_{i}(h)$ be the probability that job $i$ is covered by hyper-edge $h$ out of all hyper-edges. Additionally, the adversary deletes $\mathop{\textnormal{d}}\nolimits$ machines during the updates.

Initially, each job is covered by an arbitrary hyper-edge connected to it. Then, at each step, the adversary chooses one machine to delete. The chosen machine is removed, and any hyper-edge that includes this machine is also removed. Our cover might not be valid now; If a job $i$ was covered by one of those hyper-edges that we delete, then we need to cover it by a different hyper-edge. If this job has remaining hyper-edges, we randomly select one of the remaining hyper-edges incident to it to cover it. We draw the new hyper-edge for $i$ according to the normalized probabilities of the remaining hyper-edges. Specifically, if $H(i)$ is the set of hyper-edges still available for job $i$ , then the new probability that $i$ is covered by hyper-edge $h\in H(i)$ is:

\displaystyle\hat{p_{i}}(h)=\frac{p_{i}(h)}{\sum_{h^{\prime}\in H(i)}{p_{i}(h^% {\prime})}}\ .

This process continues until the adversary deletes $\mathop{\textnormal{d}}\nolimits$ machines in total.

Let $H y p e r R e c o u r s e$ be a random variable equals to the total recourse against an adaptive adversary in this setting (for a given bipartite hyper-graph that we do not explicitly indicate in our notation).

Let $\Delta$ be the maximal degree of a machine. Let $p^{min}$ be the minimal non-zero (initial) probability of a hyper-edge, of any job, i.e. $p^{min}=\min_{i\in\mathop{\textnormal{M}}\nolimits,\,h\in H(i)}{p_{i}(h)}$ . (Here $H(i)$ is the initial set of hyper-edges available for job $i$ .)

We prove the following theorem:

Theorem 8 (Main theorem).

If $p^{min}\geq\frac{1}{\mathop{\textnormal{N}}\nolimits}$ and the adversary deletes at most $\mathop{\textnormal{d}}\nolimits$ machines then

\displaystyle Pr\Big{[}HyperRecourse>16(\mathop{\textnormal{d}}\nolimits+% \mathop{\textnormal{M}}\nolimits)\log_{2}{\mathop{\textnormal{N}}\nolimits}\,% \Big{]}\leq\exp{\Big{(}-\,\mathop{\textnormal{M}}\nolimits\,\ln{\mathop{% \textnormal{N}}\nolimits}\,\Big{)}}

and each deletion is handled in $O(\Delta\cdot\log{\mathop{\textnormal{N}}\nolimits})$ worst-case time.

We first prove this bound in the simpler setting where each hyper-edge consists of exactly one machine, i.e. the hyper-graph is in fact a bipartite graph. This is the same balls-and-bins setting from the previous section, except that each ball (job) now has its own probability distribution over the bins (machines), instead of a uniform distribution. (Technically, the distribution is over the edges incident to each ball $b$ , but we associate the probability of each edge $(b,j)$ with bin $j$ and denote it $p_{b}(j)$ . If there is no edge from $b$ to bin $i$ then we set $p_{b}(i)=0$ .) In this simplified setting we still refer to jobs as “balls”, to machines as “bins”, and $R e c o u r s e$ is the random variable that counts the total number of balls re-thrown from the bins deleted by the adversary. In the balls and bins setting, $\Delta$ is equivalent to the maximal possible load of a single bin. We prove:

Theorem 9.

If $p^{min}\geq\frac{1}{\mathop{\textnormal{N}}\nolimits}$ and for at most $\mathop{\textnormal{d}}\nolimits$ deletions by an adaptive adversary:

\displaystyle Pr\Big{[}Recourse>16(\mathop{\textnormal{d}}\nolimits+\mathop{% \textnormal{M}}\nolimits)\log_{2}{\mathop{\textnormal{N}}\nolimits}\,\Big{]}% \leq\exp{\Big{(}-\,\mathop{\textnormal{M}}\nolimits\,\ln{\mathop{\textnormal{N% }}\nolimits}\,\Big{)}}

and each deletion is handled in $O(\Delta\cdot\log{\mathop{\textnormal{N}}\nolimits})$ worst-case time.

As in the previous section we first assume that the adversary is oblivious and deletes the bins in the order determined by a permutation $\pi$ (that is $\pi(1),\pi(2),\ldots$ ) until $\mathop{\textnormal{d}}\nolimits$ bins are deleted. For simplicity, we fix $\pi$ to be the identity so we first delete bin $1$ , then $2$ until bin $\mathop{\textnormal{d}}\nolimits$ . In practice, we bound the recourse against an adversary that follows $\pi$ until all bins are deleted, as if $\mathop{\textnormal{d}}\nolimits=\mathop{\textnormal{N}}\nolimits$ . This upper bound on the recourse trivially applies to the recourse of only $\mathop{\textnormal{d}}\nolimits$ deletions.

Let $Recourse(\pi)$ be a random variable for the total recourse against an oblivious adversary following $\pi$ . We prove the following:

Theorem 10.

For any $r\geq 1$ , if $p^{min}\geq\frac{1}{\mathop{\textnormal{N}}\nolimits}$ , then:

\displaystyle Pr\Big{[}Recourse(\pi)>16\,r\mathop{\textnormal{M}}\nolimits\log% _{2}{\mathop{\textnormal{N}}\nolimits}\Big{]}\leq\exp{\Big{(}-r\mathop{% \textnormal{M}}\nolimits\ln{\mathop{\textnormal{N}}\nolimits}\,\Big{)}}

As in the previous section we focus on a single ball $b$ and the recourse caused due to its movements. For $j_{1}\leq j_{2}$ , let $p_{b}[j_{1},j_{2}]=\sum_{j=j_{1}}^{j_{2}}{p_{b}(j)}$ be the total probability that ball $b$ assigns to bins $j_{1}$ through $j_{2}$ . If $j_{1}>j_{2}$ , we set $p_{b}[j_{1},j_{2}]=0$ . We have to define the phases more carefully as follows.

Definition 11 (Phases).

For ball $b$ , partition the sequence of bins into disjoint phases, each is an interval of consecutive bins. We define $q_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ , the first bin of phase $\mathop{\textnormal{$\phi$}}\nolimits$ , and then phase $\mathop{\textnormal{$\phi$}}\nolimits$ consists of the bins in the interval $[q_{b}(\mathop{\textnormal{$\phi$}}\nolimits),\,q_{b}(\mathop{\textnormal{$% \phi$}}\nolimits+1)-1]$ . We set $q_{b}(1)=1$ (the first bin), and then for $\mathop{\textnormal{$\phi$}}\nolimits\geq 1$ , if $p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\phi$}}\nolimits),\,\mathop{% \textnormal{N}}\nolimits\,\Big{]}>0$ and $q_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\leq N$ , let $\beta\geq q_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ be the bin such that

\displaystyle p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\phi$}}\nolimits),\,% \beta-1\,\Big{]}<0.5\cdot p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\phi$}}% \nolimits),\,\mathop{\textnormal{N}}\nolimits\,\Big{]}\leq p_{b}\Big{[}\,q_{b}% (\mathop{\textnormal{$\phi$}}\nolimits),\,\beta\,\Big{]}

We set $q_{b}(\mathop{\textnormal{$\phi$}}\nolimits+1)=\beta+1$ . Notice that when $q_{b}(\mathop{\textnormal{$\phi$}}\nolimits)=\mathop{\textnormal{N}}\nolimits$ and $p_{b}[q_{b}(\mathop{\textnormal{$\phi$}}\nolimits),\,\mathop{\textnormal{N}}% \nolimits]>0$ , we set $q_{b}(\mathop{\textnormal{$\phi$}}\nolimits+1)=\mathop{\textnormal{N}}% \nolimits+1$ , so the last interval consists only of bin $N$ .

Thus, each phase ends precisely when its bins exceed half of $b$ ’s remaining probability mass. The last phase $\mathop{\textnormal{$\Phi$}}\nolimits_{b}$ for ball $b$ is the first index $\phi$ for which $p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\phi$}}\nolimits+1),\,\mathop{% \textnormal{N}}\nolimits\,\Big{]}=0$ or $q_{b}(\mathop{\textnormal{$\phi$}}\nolimits+1)=N+1$ .

Let $\#_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ be the number of bins in phase- $\mathop{\textnormal{$\phi$}}\nolimits$ with non-zero probability for ball $b$ .

We now upper bound the number of phases $\mathop{\textnormal{$\Phi$}}\nolimits_{b}$ of ball $b$ .

Lemma 12.

Recall that $\mathop{\textnormal{$\Phi$}}\nolimits_{b}$ is the number of phases for ball $b$ , and define $p_{b}^{min}=\min_{j\in[\mathop{\textnormal{N}}\nolimits]}{p_{b}(j)}$ . Then $\mathop{\textnormal{$\Phi$}}\nolimits_{b}\leq\Big{(}1+\log_{2}{\frac{1}{p_{b}^% {min}}}\Big{)}$ .

Proof.

Phases are consecutive and disjoint, so:

	$\displaystyle p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\phi$}}\nolimits+1),\,% \mathop{\textnormal{N}}\nolimits\,\Big{]}$	$\displaystyle=p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\phi$}}\nolimits),\,% \mathop{\textnormal{N}}\nolimits\,\Big{]}-p_{b}\Big{[}\,q_{b}(\mathop{% \textnormal{$\phi$}}\nolimits),\,q_{b}(\mathop{\textnormal{$\phi$}}\nolimits+1% )-1\Big{]}$
		$\displaystyle\leq p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\phi$}}\nolimits),% \,\mathop{\textnormal{N}}\nolimits\,\Big{]}-0.5\cdot p_{b}\Big{[}\,q_{b}(% \mathop{\textnormal{$\phi$}}\nolimits),\,\mathop{\textnormal{N}}\nolimits\,% \Big{]}$
		$\displaystyle=0.5\cdot p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\phi$}}% \nolimits),\,\mathop{\textnormal{N}}\nolimits\,\Big{]}$

Repeatedly applying this halving argument shows that $p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\Phi$}}\nolimits_{b}),\,\mathop{% \textnormal{N}}\nolimits\,\Big{]}\leq(0.5)^{\mathop{\textnormal{$\Phi$}}% \nolimits_{b}-1}p_{b}\big{[}\,1,\mathop{\textnormal{N}}\nolimits\,\big{]}=(0.5% )^{\mathop{\textnormal{$\Phi$}}\nolimits_{b}-1}$ . Clearly $p_{b}^{min}\leq p_{b}\Big{[}\,q_{b}(\mathop{\textnormal{$\Phi$}}\nolimits_{b})% ,\mathop{\textnormal{N}}\nolimits\,\Big{]}$ so $p_{b}^{min}\leq(0.5)^{\mathop{\textnormal{$\Phi$}}\nolimits_{b}-1}$ and $\mathop{\textnormal{$\Phi$}}\nolimits_{b}\leq\Big{(}1+\log_{2}{\frac{1}{p_{b}^% {min}}}\Big{)}$ . $\hfill\blacktriangleleft$

We also need the following definitions. Let $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ be a random variable counting the recourse ball $b$ incurs during phase $\mathop{\textnormal{$\phi$}}\nolimits$ . If ball $b$ never lands in any bin of phase $\mathop{\textnormal{$\phi$}}\nolimits$ , then $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)=0$ . The following lemma upper bounds $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ .

Lemma 13.

$R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\preceq\big{(}\,2+Geo(0.5)\,\big{)}$ , i.e. $Pr\Big{[}\,R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)>u\,\Big{]}\leq Pr\Big{% [}\big{(}2+Geo(0.5)\,\big{)}>u\,\Big{]}$ for all $u\in(-\infty,\infty)$ .

Proof.

Let $R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)$ be a random variable that counts the number of bins that ball $b$ changed during phase $\mathop{\textnormal{$\phi$}}\nolimits$ , not including the last bin deleted in the phase, that is the bin at position $q_{\mathop{\textnormal{$\phi$}}\nolimits+1}-1$ . We call these bins the internal bins of phase $\phi$ . Since both $R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)$ and $Geo(0.5)$ can only receive integer values, it is enough to prove the statement for integer values of $u$ . Since $R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)\geq 0$ , the claim is trivial for $u<0$ . Also, the recourse of a single ball in a phase cannot be greater than the number of bins of that phase with non-zero probability, i.e. $R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)\leq\#_{b}(\mathop{% \textnormal{$\phi$}}\nolimits)$ , so the claim is trivial for $u\geq\#_{b}(\mathop{\textnormal{$\phi$}}\nolimits)$ as well. We use induction on $u\in\Big{[}0,\,\#_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\,\Big{]}$ to show that $Pr\Big{[}\,R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)>u\,\Big{]}% \leq Pr\Big{[}\,\big{(}1+Geo(0.5)\,\big{)}>u\,\Big{]}$ for the remaining integer values of $u$ . From this the lemma follows, since $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\leq 1+R_{b}^{\prime}(\mathop{% \textnormal{$\phi$}}\nolimits)$ and therefore $R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)\preceq 1+R_{b}^{\prime}(\mathop{% \textnormal{$\phi$}}\nolimits)\preceq 2+Geo(0.5)$ . The induction is as follows.

Base case ( $u=0$ ).

This holds trivially since $Pr\Big{[}\big{(}2+Geo(0.5)\big{)}>0\Big{]}=1$ .

Let $STAYIN(\mathop{\textnormal{$\phi$}}\nolimits,\,u-1)$ be the event that, after $u-1$ such re-throws, ball $b$ is still in a phase- $\mathop{\textnormal{$\phi$}}\nolimits$ ’s bin.

Inductive step.

Assume it holds for $u-1$ , i.e. $Pr\Big{[}R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)>u-1\Big{]}\leq Pr% \Big{[}\big{(}1+Geo(0.5)\big{)}>u-1\Big{]}$ .
Thus, for $u>0$ :

	$\displaystyle Pr\Big{[}R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)>u% \,\Big{]}$	$\displaystyle=Pr\Big{[}R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)>u% -1\cap STAYIN(\phi,\,u-1)\Big{]}$
		$\displaystyle=Pr\Big{[}R_{b}^{\prime}(\mathop{\textnormal{$\phi$}}\nolimits)>u% -1\Big{]}\cdot Pr\Big{[}STAYIN(\phi,\,u-1)\,\|\,R_{b}(\mathop{\textnormal{$\phi% $}}\nolimits)>u-1\Big{]}$
		$\displaystyle\leq Pr\Big{[}\big{(}1+Geo(0.5)\big{)}>u-1\Big{]}\cdot Pr\Big{[}% STAYIN(\phi,\,u-1)\,\|\,R_{b}(\mathop{\textnormal{$\phi$}}\nolimits)>u-1\Big{]}$
		$\displaystyle\leq Pr\Big{[}\big{(}1+Geo(0.5)\big{)}>u-1\Big{]}\cdot 0.5=Pr\Big% {[}\big{(}1+Geo(0.5)\big{)}>u\Big{]}.$

Where the $0.5$ bound in the second inequality follows from the way we defined the phases. In particular the total probability (according to $p_{b}$ ) of the internal bins of a phase is at most half of the total probability of all remaining bins. Thus, when the ball is re-thrown according to the normalized probabilities, it lands in an internal bin of phase $\phi$ with probability at most $0.5$ . $\hfill\blacktriangleleft$

We are now ready to focus on the total recourse of all $\mathop{\textnormal{M}}\nolimits$ balls for the deletion order $\pi$ , and prove Theorem 10:

Proof of Theorem 10.

Note that all variables $R_{i}(\mathop{\textnormal{$\phi$}}\nolimits)$ are independent: the recourse of a single ball does not affect the recourse of other balls, and a ball’s recourse in one phase does not affect its recourse in another phase. Thus, we can use Theorem 6 and Lemma 13.

By Lemma 13, for every ball $i$ and every phase $\mathop{\textnormal{$\phi$}}\nolimits$ we have

R_{i}(\mathop{\textnormal{$\phi$}}\nolimits)\preceq\big{(}2+Geo(0.5)\,\big{)}.

Let $A=\sum_{i=1}^{\mathop{\textnormal{M}}\nolimits}{\mathop{\textnormal{$\Phi$}}% \nolimits_{i}}$ . Therefore:

	$\displaystyle Recourse(\pi)$	$\displaystyle=\sum_{i=1}^{\mathop{\textnormal{M}}\nolimits}{\sum_{\mathop{% \textnormal{$\phi$}}\nolimits=1}^{\mathop{\textnormal{$\Phi$}}\nolimits_{i}}{R% _{i}(\mathop{\textnormal{$\phi$}}\nolimits)}}\preceq\sum_{i=1}^{\mathop{% \textnormal{M}}\nolimits}{\sum_{\mathop{\textnormal{$\phi$}}\nolimits=1}^{% \mathop{\textnormal{$\Phi$}}\nolimits_{i}}{\Big{(}2+Geo(0.5)\,\Big{)}}}$
		$\displaystyle=\Big{(}2+Geo(0.5)\,\Big{)}\cdot\sum_{i=1}^{\mathop{\textnormal{M% }}\nolimits}{\mathop{\textnormal{$\Phi$}}\nolimits_{i}}=2A+GS\Big{(}A,\,0.5% \Big{)}$

Where $GS\Big{(}A,\,0.5\Big{)}$ is the sum of $A\,$ i.i.d. geometrically distributed random variables.

By Lemma 12, $A\leq\sum_{b=1}^{M}\Big{(}1+\log_{2}{\frac{1}{p_{b}^{min}}}\Big{)}$ . Since by our definitions $p_{b}^{min}\geq p^{min}$ and since we assume that $p^{min}\geq\frac{1}{\mathop{\textnormal{N}}\nolimits}$ , we can conclude that $A\leq\mathop{\textnormal{M}}\nolimits\cdot(1+\log_{2}{\mathop{\textnormal{N}}% \nolimits}\ )$ .

Let $k=\frac{8r\mathop{\textnormal{M}}\nolimits\log_{2}{\mathop{\textnormal{N}}% \nolimits}}{A}-1$ . Note that $k\geq 3$ because $r\geq 1$ , $\mathop{\textnormal{N}}\nolimits\geq 2$ and $A\leq\mathop{\textnormal{M}}\nolimits\cdot(1+\log_{2}{\mathop{\textnormal{N}}% \nolimits}\ )\leq 2M\log_{2}{\mathop{\textnormal{N}}\nolimits}$ .

Applying Theorem 7 for the sum of geometric random variables, using $k$

	$\displaystyle Pr\Big{[}Recourse(\pi)>16\,r\mathop{\textnormal{M}}\nolimits\log% _{2}{\mathop{\textnormal{N}}\nolimits}\Big{]}$	$\displaystyle=Pr\Big{[}Recourse(\pi)>2A\cdot(k+1)\Big{]}$
		$\displaystyle\leq Pr\Big{[}\,2A+GS\Big{(}A,\,0.5\Big{)}>2A\cdot(k+1)\,\Big{]}$
		$\displaystyle=Pr\Big{[}\,GS\Big{(}A,\,0.5\Big{)}>\frac{k\cdot A}{0.5}\,\Big{]}% \leq\exp{\Big{(}-\frac{(1-1/k)^{2}}{2}\cdot kA\Big{)}}$
		$\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mu1\mkern-1.5% mu)}}{{\leq}}\exp{\Big{(}-\frac{1}{8}\cdot(8r\mathop{\textnormal{M}}\nolimits% \log_{2}{\mathop{\textnormal{N}}\nolimits}-A)\Big{)}}\stackrel{{\scriptstyle% \scriptscriptstyle(\mkern-1.5mu2\mkern-1.5mu)}}{{\leq}}\exp{\Big{(}-\frac{1}{8% }\cdot 6r\mathop{\textnormal{M}}\nolimits\log_{2}{\mathop{\textnormal{N}}% \nolimits}\,\Big{)}}$
		$\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mu3\mkern-1.5% mu)}}{{\leq}}\exp{\Big{(}-r\mathop{\textnormal{M}}\nolimits\ln{\mathop{% \textnormal{N}}\nolimits}\,\Big{)}}\ .$

Inequality (1) follows since $\frac{(1-1/k)^{2}}{2}\geq\frac{1}{8}$ for $k\geq 3$ , Inequality (2) follows since $A\leq 2M\log_{2}{\mathop{\textnormal{N}}\nolimits}$ , and Inequality (3) follows since $6/(8\ln(2))\geq 1$ . $\hfill\blacktriangleleft$ We now prove our main theorem, Theorem 9:

Proof of Theorem 9.

First, notice that when the adversary deletes bin $b$ , the update time of each ball in bin $b$ is $O(\log{\mathop{\textnormal{N}}\nolimits})$ , as the ball randomly selects a new bin (using standard binary search on the cumulative probabilities), or removed in the case that no bins that can reside it are left. Thus, the update time of each deletion is $O(\Delta\cdot\log{\mathop{\textnormal{N}}\nolimits})$ .

We now bound the recourse for exactly $\mathop{\textnormal{d}}\nolimits$ adaptive deletions, and the proof for less than $\mathop{\textnormal{d}}\nolimits$ deletions follows. Out of $\mathop{\textnormal{N}}\nolimits$ total bins, $\mathop{\textnormal{d}}\nolimits$ bins are deleted by the adversary. There are $\binom{\mathop{\textnormal{N}}\nolimits}{\mathop{\textnormal{d}}\nolimits}\,(% \mathop{\textnormal{d}}\nolimits)!$ distinct ways to pick and order these $\mathop{\textnormal{d}}\nolimits$ bins. If any of these ordered $d$ deletions causes a high recourse then the recourse of any oblivious adversary that deletes all bins by any permutation that extends these $d$ deletions is high. Thus, it follows by the union bound and Theorem 10 with $r=\frac{\mathop{\textnormal{d}}\nolimits}{\mathop{\textnormal{M}}\nolimits}+1\geq 1$ , that the probability that any of these orders produces recourse above $16(\mathop{\textnormal{d}}\nolimits+\mathop{\textnormal{M}}\nolimits)\log_{2}{% \mathop{\textnormal{N}}\nolimits}$ is:

	$\displaystyle Pr\big{[}$	$\displaystyle\text{There is an order of $d$ deletions with recourse greater % than }16(\mathop{\textnormal{d}}\nolimits+\mathop{\textnormal{M}}\nolimits)% \log_{2}{\mathop{\textnormal{N}}\nolimits}\,\big{]}$
		$\displaystyle=Pr\big{[}\text{There is an order of $d$ deletions with recourse % greater than }16(\frac{\mathop{\textnormal{d}}\nolimits}{\mathop{\textnormal{M% }}\nolimits}+1)\mathop{\textnormal{M}}\nolimits\log_{2}{\mathop{\textnormal{N}% }\nolimits}\,\big{]}$
		$\displaystyle\leq\binom{\mathop{\textnormal{N}}\nolimits}{\mathop{\textnormal{% d}}\nolimits}\cdot(\mathop{\textnormal{d}}\nolimits)!\cdot\exp{\Big{(}-(\frac{% \mathop{\textnormal{d}}\nolimits}{\mathop{\textnormal{M}}\nolimits}+1)\mathop{% \textnormal{M}}\nolimits\ln{\mathop{\textnormal{N}}\nolimits}\,\Big{)}}=\frac{% \mathop{\textnormal{N}}\nolimits!}{(\mathop{\textnormal{N}}\nolimits-\mathop{% \textnormal{d}}\nolimits)!}\cdot\exp{\Big{(}-(\mathop{\textnormal{d}}\nolimits% +\mathop{\textnormal{M}}\nolimits)\ln{\mathop{\textnormal{N}}\nolimits}\Big{)}}$
		$\displaystyle\leq\mathop{\textnormal{N}}\nolimits^{\,\mathop{\textnormal{d}}% \nolimits}\cdot\exp{\Big{(}-(\mathop{\textnormal{d}}\nolimits+\mathop{% \textnormal{M}}\nolimits)\ln{\mathop{\textnormal{N}}\nolimits}\,\Big{)}}=\exp{% \Big{(}\big{(}\mathop{\textnormal{d}}\nolimits-(\mathop{\textnormal{d}}% \nolimits+\mathop{\textnormal{M}}\nolimits)\big{)}\,\ln{\mathop{\textnormal{N}% }\nolimits}\,\Big{)}}=\exp{\Big{(}-\,\mathop{\textnormal{M}}\nolimits\,\ln{% \mathop{\textnormal{N}}\nolimits}\,\Big{)}}.$

Finally, we adapt the argument from the uniform-bins case to show that an adaptive adversary cannot do better. We simulate all possible deletion paths in parallel, revealing the state of the bins to the adversary at each node of this decision tree. If there was a high-recourse path, it would appear among the $\binom{\mathop{\textnormal{N}}\nolimits}{\mathop{\textnormal{d}}\nolimits}\,(% \mathop{\textnormal{d}}\nolimits)!$ oblivious orders and we bounded the probability that this happens. Hence, the theorem follows. $\hfill\blacktriangleleft$ Returning to the original hyper-edge setting: if a hyper-edge $h$ connects multiple machines, its effective “deletion time” in a fixed permutation $\pi$ is given by the first machine among $h$ ’s machines to be deleted. After that, the rest of $h$ ’s machines are irrelevant for $h$ itself, since $h$ is already removed. Thus, once the deletion order $\pi$ is fixed, each hyper-edge effectively acts like a single-machine edge in terms of determining when it disappears. Consequently, the hyper-edge setting can be reduced to a multi-probability-distribution “balls and bins” model presented above. Concretely, let $S_{i}(j)$ be the set of hyper-edges that connect job $i$ to machine $j$ , and for which $j$ is the first machine to be deleted among these hyper-edges. Then, for ball (job) $i$ and bin (machine) $j$ , the equivalent probability is given by $p_{i}(j)=\sum_{h\in S}{p_{i}(h)}$ .

All arguments carry through essentially unchanged, leading to
$HyperRecourse\,\leq\,16\,(\mathop{\textnormal{d}}\nolimits+\mathop{\textnormal% {M}}\nolimits)\,\log_{2}(\mathop{\textnormal{N}}\nolimits)$ with high probability. This completes the proof of Theorem 8.

4 Fully Dynamic 3-Spanner Against Adaptive Adversary

For completeness before we start, we repeat the definition of $k$ spanner of a graph $G$ : This is a subgraph $H$ of $G$ on the same set of vertices as $G$ such that the distance between any pair of vertices in $H$ is larger than in $G$ by a factor of at most $k$ . For more information about spanners see e.g. [4, 36, 7, 22, 37, 14, 13].

In this section we apply our decremental load balancing framework to maintain a $3$ -spanner against an adaptive adversary which performs insertions and deletions of edges to the graph. We prove the following theorem:

Theorem 14.

There is a randomized algorithm that, given an unweighted graph $G(V,E)$ with $|V|=n$ vertices and $|E|=m$ edges undergoing edge insertions and deletions by an adaptive adversary, maintains a 3-spanner of $G$ . This spanner has $O(n\sqrt{n})$ edges and is maintained with $O(\sqrt{n}\cdot\log{n})$ worst-case update time. Furthermore, the algorithm achieves $O(\log{n})$ amortized recourse with high probability.

4.1 Algorithm Description

Static Construction

We begin with a static 3-spanner construction for $G(V,\,E)$ . Let $N_{G}(u)$ be the set of neighbors of vertex $u$ . Partition $V$ arbitrarily into $\sqrt{n}$ equal-sized buckets $V_{1},...,V_{\sqrt{n}}$ , each of size $\sqrt{n}$ . We construct three edge sets $E_{1},E_{2},E_{3}$ as follows:

$\blacksquare$

Set $E_{1}$ : For each bucket $V_{\ell}$ , $\ell\in[\sqrt{n}\,]$ , and every vertex $v\in V\setminus V_{\ell}$ such that $N_{G}(v)\cap V_{\ell}\neq\emptyset$ , choose an arbitrary neighbor $c_{\ell}(v)\in V_{\ell}\cap N_{G}(v)$ and add $\big{(}v,\,c_{\ell}(v)\big{)}$ to $E_{1}$ . We call $c_{\ell}(v)$ the $\ell$ -partner of $v$ .
$\blacksquare$

Set $E_{2}$ : For each edge $e=(u,v)$ where $u,v\in V_{\ell}$ (i.e. both in the same bucket), add $e$ to $E_{2}$ .
$\blacksquare$

Set $E_{3}$ : For any pair of vertices $u,u^{\prime}\in V_{\ell}$ that share at least one neighbor, pick an arbitrary common neighbor $w_{uu^{\prime}}\in N_{G}(u)\cap N_{G}(u^{\prime})$ and add the edges $(u,w_{uu^{\prime}})$ and $(w_{uu^{\prime}},u^{\prime})$ to $E_{3}$ . We refer to $w_{uu^{\prime}}$ as the witness for $(u,u^{\prime})$ .

Claim 15.

The subgraph $F^{\prime}=(V,\,E_{1}\cup E_{2}\cup E_{3})$ is a 3-spanner of $G$ with $O(n\sqrt{n})$ edges.

Proof.

We show that every edge $(u,v)\in E$ has a path of length at most 3 in $F^{\prime}$ . If $u$ and $v$ are in the same bucket, then $(u,v)\in E_{2}$ , so the claim is immediate.

Otherwise, suppose $u\in V_{\ell}$ , $v\in V_{\ell^{\prime}}$ . If $(u,v)\in E_{1}$ because $u$ is the $\ell^{\prime}$ -partner of $v$ (or vice versa), then we are done. Otherwise, there must be another vertex $u^{\prime}\in V_{\ell}$ serving as the $\ell^{\prime}$ -partner of $v$ , i.e. $(u^{\prime},v)\in E_{1}$ , and $u,u^{\prime}$ share the neighbor $v$ . Hence there is a witness $w_{uu^{\prime}}$ with edges $(u,w_{uu^{\prime}}),(w_{uu^{\prime}},u^{\prime})\in E_{3}$ , giving a path $(u,w_{uu^{\prime}}),(w_{uu^{\prime}},u^{\prime}),(u^{\prime},v)$ of length 3 between $u$ and $v$ .

Next, we bound $|E_{1}|,\,|E_{2}|,$ and $|E_{3}|$ . Each vertex has at most one partner per bucket, so $|E_{1}|=O(n\sqrt{n})$ . Each bucket has at most $\sqrt{n}\times\sqrt{n}=n$ internal edges, with $\sqrt{n}$ buckets, giving $|E_{2}|=O(n\sqrt{n})$ . In each bucket, there are at most $n$ vertex pairs, each contributing up to 2 edges in $E_{3}$ , so $|E_{3}|=O(n\sqrt{n})$ . Altogether, $|E_{1}\cup E_{2}\cup E_{3}|=O\big{(}n\sqrt{n}\big{)}$ . $\hfill\vartriangleleft$

Dynamic Maintenance

Our approach is based on the static algorithm of [38] with the modifications by [20], adapted to handle edge insertions and deletions in $G$ . We maintain $E_{1},\,E_{2},$ and $E_{3}$ separately as the adversary add or remove edges from $G$ . To handle updates efficiently we maintain for each vertex $v$ a data structure called neighbors-dictionary, that groups the neighbors of $v$ to $\sqrt{n}$ sets, one set for each bucket. When an edge $(u,u^{\prime})$ is added or deleted, where $u\in V_{\ell}$ and $u^{\prime}\in V_{\ell^{\prime}}$ , we only need to update the dictionary entries for $u$ and $u^{\prime}$ . Specifically, we add or remove $u^{\prime}$ from the set of neighbors of $u$ in bucket $\ell^{\prime}$ and do the same for $u$ in bucket $\ell$ of $u^{\prime}$ . Since these operations involve simple insertions or deletions in a dictionary¹¹1We represent these dictionaries as search trees. This would work also in a computational model that does not allow dynamic hashing data structures. If we do allow them then it can take $O(1)$ time, they run in $O(\log{n})$ worst-case time.

Maintaining $E_{1}$ and $E_{2}$

When the adversary deletes an edge $\big{(}u,c_{\ell}(u)\big{)}$ , we find a new (arbitrary) $\ell$ -partner for $u$ (if one exists) using the neighbors-dictionary of $u$ and add it to $E_{1}$ . If an edge $(u,u^{\prime})$ with $u\in V_{\ell},u^{\prime}\in V_{\ell^{\prime}}$ is inserted and $u$ does not have an $\ell^{\prime}$ -partner, we set $c_{\ell^{\prime}}(u)=u^{\prime}$ and add $(u,u^{\prime})$ to $E_{1}$ .

The maintenance of $E_{2}$ is straightforward. These operations takes $O(\log{n})$ time.

Maintaining $E_{3}$ : Deletions vs. Insertions

To handle $E_{3}$ in a fully dynamic setting, we partition the sequence of updates into epochs, each containing $n\sqrt{n}$ updates. Let $E_{\mathrm{Inserted}}$ be the edges newly added during an epoch. It suffices to maintain a 3-spanner $F^{\prime}(V,\,E^{\prime})$ that only handles deletions in $E_{3}$ throughout the epoch. Since $F\big{(}V,\,E^{\prime}\cup E_{\mathrm{Inserted}}\big{)}$ remains a 3-spanner of $G$ (This follows from the decomposability property of spanners, namely that the union of two spanners of sub-graphs is itself a spanner of the union of those sub-graphs). We maintain $E_{\mathrm{Inserted}}$ since we may need to delete edges from it (if we delete an edge which was inserted in the same epoch). The list $E_{\mathrm{Inserted}}$ is of size $O(n\sqrt{n})$ so the union $F$ has at most $n\sqrt{n}$ edges which are not in $F^{\prime}$ , preserving our desired size. Hence, we only need to address deletions of $E_{3}$ edges within each epoch and to describe how we initialize an epoch to reflect newly inserted edges in the previous epoch.

Deletions in $E_{3}$

When $(u,w_{uu^{\prime}})\in E_{3}$ is deleted and the pair $u,u^{\prime}$ still share a neighbor, we must pick a new witness for the pair $u,u^{\prime}$ . We use the decremental load balancing framework to do so. Specifically, we form a bipartite hyper-graph, denoted by $H$ , representing pairs $(u,u^{\prime})$ which are in the same bucket and their common neighbors:

$\blacksquare$

For each pair $(u,u^{\prime})$ in the same bucket, create a job $\mathcal{J}(u,u^{\prime})$ on one side of $H$ . Because each bucket has $\sqrt{n}$ vertices and there are $\sqrt{n}$ buckets, we have $\mathop{\textnormal{M}}\nolimits=n\sqrt{n}$ jobs in total.
$\blacksquare$

For each edge $e\in E$ , create a machine $\mathcal{M}(e)$ on the other side of $H$ , yielding $\mathop{\textnormal{N}}\nolimits=m$ machines.
$\blacksquare$

A hyper-edge connects $\mathcal{J}(u,u^{\prime})$ to $\mathcal{M}(e)$ and $\mathcal{M}(e^{\prime})$ if $u,u^{\prime}$ (of the same bucket) share a neighbor via the edges $e$ and $e^{\prime}$ .

A valid covering of the jobs by hyper-edges corresponds exactly to a valid set of witness edges in $E_{3}$ . Each pair $(u,u^{\prime})$ with a common neighbor is covered by a hyper-edge that corresponds to a witness. Thus, we maintain a feasible cover of all jobs under machine (edge) deletions. Specifically, for each job $\mathcal{J}(u,u^{\prime})$ , let $\mathcal{H}(u,u^{\prime})$ be the hyper-edges incident to it, and define

p_{\mathcal{J}(u,u^{\prime})}(h)\;=\;\begin{cases}\frac{1}{|\mathcal{H}(u,u^{% \prime})|},&\text{if }h\in\mathcal{H}(u,u^{\prime}),\\ 0,&\text{otherwise}.\end{cases}

After each deletion of a machine (edge), we remove all hyper-edges that are incident to the deleted machine. Then, we draw new edges for each job that lost its covering hyperedge but still has hyperedges incident to it. As in the decremental load balancing framework, we draw an edge according to the normalized probability distribution of this job (which is uniform on its remaining hyperedges). The job cover at any one time defines our set of witnesses and thereby the edges in $E_{3}$ .

We analyze the recourse incurred by adversarial deletions within a single epoch using Theorem 8. Since each job $\mathcal{J}(u,u^{\prime})$ has less than $n$ hyper-edges, one hyper-edge for each common neighbor, we have $p_{\mathcal{J}(u,u^{\prime})}(h)\geq 1/n\geq 1/m=1/\mathop{\textnormal{N}}\nolimits$ , meeting the conditions of Theorem 8. The adversary deletes at most $n\sqrt{n}$ machines during an epoch, so we can use Theorem 8 with $\mathop{\textnormal{d}}\nolimits=n\sqrt{n}$ . Let $E p o c h R e c o u r s e$ be the total recourse incurred in a single epoch against an adaptive adversary. By Theorem 8, we have:

	$\displaystyle Pr\Big{[}EpochRecourse>64n\sqrt{n}\log_{2}{n}\Big{]}$	$\displaystyle\leq Pr\Big{[}EpochRecourse>16(\mathop{\textnormal{d}}\nolimits+% \mathop{\textnormal{M}}\nolimits)\log_{2}{\mathop{\textnormal{N}}\nolimits}\,% \Big{]}$
		$\displaystyle\leq\exp\Big{(}-\mathop{\textnormal{M}}\nolimits\ln{\mathop{% \textnormal{N}}\nolimits}\Big{)}\leq\exp\Big{(}-n\sqrt{n}\ln{m}\,\Big{)}.$

Hence, with high probability, the amortized recourse per epoch is $O(\log n)$ .

In order to bound the update time we need the following lemma:

Lemma 16.

Let $\Delta$ be the maximum degree of a machine in $H$ . Then $\Delta=O(\sqrt{n})$ .

Proof of Lemma 16.

Each machine $\mathcal{M}(e)$ corresponds to an edge $(u,u^{\prime})\in E$ , where $u\in V_{\ell}$ and $u^{\prime}\in V_{\ell^{\prime}}$ (possibly $\ell=\ell^{\prime}$ ). The machine $\mathcal{M}(e)$ can appear in hyper-edges that connects to jobs of the form $\mathcal{J}(u,x)$ for $x\in V_{\ell}$ or $\mathcal{J}(u^{\prime},y)$ for $y\in V_{\ell^{\prime}}$ . Since each bucket contains at most $\sqrt{n}$ vertices, the number of jobs associated with a machine is at most $2\sqrt{n}$ . Thus, $\Delta=O(\sqrt{n})$ . $\hfill\blacktriangleleft$ So, by Theorem 8 and Lemma 16, the worst-case update time for maintaining $E_{3}$ is $O(\sqrt{n}\cdot\log{n})$ .

Notice that the hyper-graph has a size of $O(n^{2.5})$ , which aligns with the size of the Partnership Data Structures from [20].

Epoch Initialization

To complete the description of the data structure we need to describe how to initialize an epoch. We need to start each epoch with a hyper-graph and a job cover that accurately represents the current state of $G$ , and take into account all edges inserted in the previous epoch which we collected in a separate list. Specifically, we have to update the hyper-graph’s machines and hyper-edges to incorporate newly added edges to $G$ from the previous epoch. In addition, we may have to add hyper-edges to the cover such that it remains valid (this corresponds to updating the set of witness and and their incident edges in $E_{3}$ to be a valid one).

We first describe the update process for a single edge (inserted in the previous epoch):

1.

Machine Creation. We add a machine for each new edge.
2.

Hyper-edge Updates. We add hyper-edges to represent new common neighbors: Let $\mathcal{M}\big{(}(u,u^{\prime})\big{)}$ be the newly created machine for the edge $(u,u^{\prime})$ where $u\in V_{\ell}$ and $u^{\prime}\in V_{\ell^{\prime}}$ . We identify these new hyperedges by traversing $u^{\prime}$ ’s neighbors from bucket $\ell$ and $u$ ’s neighbors from bucket $\ell^{\prime}$ . When we add an edge incident to a job that currently has not hyperedge in the cover we add the edge to the cover as well. Since each bucket has $O(\sqrt{n})$ vertices, then the update time is $O(\sqrt{n}\log{n})$ . During the entire reintialization (processing all inserted edges) we add to the cover at most $O(n\sqrt{n})$ edges which we can charge to the update operations during the epoch, thus maintaining the recourse bound of $O(\log n)$ with high probability. Notice that when we delete an edge $e$ which was inserted in the same epoch we have to find it in the list of inserted edges, $E_{\mathrm{Inserted}}$ , and delete it from this list. This would take $O(\log n)$ time if we represent this list as a search tree.

Amortize Initialization to Worst-Case

Notice that performing all the insertions of the previous epoch at the beginning of the new epoch leads to $O(\sqrt{n})$ amortized update time. Instead, we can execute these updates “in the background” and get good worst case update time. For this we utilize two copies of the hyper-graph. The first copy represents the state of $G$ at the beginning of the epoch, and is used for the decremental maintenance of $E_{3}$ during the epoch using the simple load balancing algorithm. The second copy initially does not include the edges inserted (and not deleted) in previous epoch. During the current epoch it is updated by the deletions and insertions that the adversary does, and in addition we add the edges inserted in the previous epoch, a constant number of such insertions per update of the current epoch. At the beginning of the next epoch, the second copy represents the state of $G$ , so both copies switch roles. Overall, with this incremental rebuilding each update takes $O(\sqrt{n}\log{n})$ worst-case time.

This completes the proof of Theorem 14.

5 Concluding remarks

Our results provide a new perspective on adaptivity in dynamic algorithms: sometimes, complex schemes to hide randomness from the adversary may not be necessary if we can show that the adversary is not as powerful as it appears. We demonstrated this within the load-balancing framework and applied it to obtain a simple construction of a $3$ -spanner against an adaptive adversary.

As we suggested in the introduction, there are several other simple algorithms one might consider for the load-balancing game. We suspect that some of these algorithms share similar properties with the one we analyzed. However, their analysis appears more challenging due to additional dependencies and may require developing new general tools. For example, one might consider an algorithm that partitions the balls in the deleted bin into two equal-sized groups and assigns each group to a randomly chosen bin.²²2It is easy to see that moving all balls together to a single random bin can incur quadratic recourse. What is the recourse of this scheme? Of course one can also split into $k$ groups for some fixed $k>1$ . For larger $k$ we use more randomness so it may be easier to analyze. Additionally, we can consider games in which bins are not deleted but remain in the system, or schemes where the adversary forces us to redistribute only a subset of the balls in the targeted bin. Analyzing any of these simple games may provide insights and fundamental tools for handling adaptive inputs.

Bounding the worst-case recourse also remains an open challenge. Furthermore, extending this approach to maintain a general $k$ -spanner in dynamic and adaptive settings presents another intriguing direction for future research.

References

[1] Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. In PODS, pages 15–27. ACM, 2022. doi:10.1145/3517804.3526228.
[2] N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58:137–147, 1999. doi:10.1006/JCSS.1997.1545.
[3] Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. In ITCS, volume 251 of LIPIcs, pages 8:1–8:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ITCS.2023.8.
[4] Giorgio Ausiello, Paolo Giulio Franciosa, and Giuseppe F. Italiano. Small stretch spanners on dynamic graphs. J. Graph Algorithms Appl., 10(2):365–385, 2006. Announced at ESA’05. doi:10.7155/JGAA.00133.
[5] Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, and Stefan Schmid. Dynamic balanced graph partitioning. SODA, 34(3):1791–1812, 2020. doi:10.1137/17M1158513.
[6] Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. In STOC, pages 1046–1059. ACM, 2016. doi:10.1145/2897518.2897566.
[7] Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms, 8(4):35:1–35:51, 2012. Announced at SODA’08. doi:10.1145/2344422.2344425.
[8] MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In SODA, pages 2677–2727. SIAM, 2023. doi:10.1137/1.9781611977554.CH101.
[9] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In FOCS, pages 382–405, 2019. doi:10.1109/FOCS.2019.00032.
[10] Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. In SOSA, pages 214–227. SIAM, 2022. doi:10.1137/1.9781611977066.15.
[11] Omri Ben-Eliezer, Rajesh Jayaram, David P Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. In PODS, pages 63–80, 2020. doi:10.1145/3375395.3387658.
[12] Michael A. Bender, Jake Christensen, Alex Conway, Martin Farach-Colton, Rob Johnson, and Meng-Tsung Tsai. Optimal ball recycling. In SODA, pages 2527–2546. SIAM, 2018.
[13] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432, 2020. arXiv:2004.08432.
[14] Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. In SODA, pages 1899–1918, 2019. doi:10.1137/1.9781611975482.115.
[15] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In ICALP, pages 20:1–20:20, 2022. doi:10.4230/LIPICS.ICALP.2022.20.
[16] Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic dynamic matching in O(1) update time. Algorithmica, 82(4):1057–1080, 2020. doi:10.1007/S00453-019-00630-4.
[17] Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc. Online edge coloring algorithms via the nibble method. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2830–2842. SIAM, 2021. doi:10.1137/1.9781611976465.168.
[18] Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In SODA, pages 785–804. SIAM, 2015. doi:10.1137/1.9781611973730.54.
[19] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In STOC, pages 398–411. ACM, 2016. doi:10.1145/2897518.2897568.
[20] Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. In ESA, volume 244 of LIPIcs, pages 17:1–17:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.17.
[21] Guy Blanc. Subsampling suffices for adaptive data analysis. In STOC, pages 999–1012. ACM, 2023. doi:10.1145/3564246.3585226.
[22] Greg Bodwin and Sebastian Krinninger. Fully dynamic spanners with worst-case update time. In ESA, pages 17:1–17:18, 2016. doi:10.4230/LIPIcs.ESA.2016.17.
[23] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In NeurIPS, NIPS ’21. Curran Associates Inc., 2021.
[24] Daniel G. Brown. How I wasted too long finding a concentration inequality for sums of geometric variables. URL: https://cs.uwaterloo.ca/˜browndg/negbin.pdf.
[25] Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 217–226, 2016. doi:10.1145/2933057.2933083.
[26] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. Theoretical Computer Science, 312(1):3–15, 2004. Automata, Languages and Programming. doi:10.1016/S0304-3975(03)00400-6.
[27] Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In FOCS, pages 370–381, 2019. doi:10.1109/FOCS.2019.00031.
[28] Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In NeurIPS, volume 33, pages 11178–11190. Curran Associates, Inc., 2020.
[29] Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In SODA, pages 389–400, 2019. doi:10.1145/3313276.3316320.
[30] Edith Cohen, Xin Lyu, Jelani Nelson, Tamas Sarlos, Moshe Shechner, and Uri Stemmer. On the robustness of CountSketch to adaptive inputs. In ICML, volume 162, pages 4112–4140. PMLR, 2022. URL: https://proceedings.mlr.press/v162/cohen22a.html.
[31] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 4112–4140. PMLR, 2022. URL: https://proceedings.mlr.press/v162/cohen22a.html.
[32] Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58–75, 2005. doi:10.1016/j.jalgor.2003.12.001.
[33] Jimmy Z. Di, Jack Douglas, Jayadev Acharya, Gautam Kamath, and Ayush Sekhari. Hidden poison: Machine unlearning enables camouflaged poisoning attacks. In NeurIPS ML Safety Workshop, 2022. URL: https://openreview.net/forum?id=zml9gDnulI9.
[34] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In NIPS, pages 2350–2358, 2015. URL: https://proceedings.neurips.cc/paper/2015/hash/bad5f33780c42f2588878a9d07405083-Abstract.html.
[35] Florian Eggenberger and George Pólya. Über die statistik verketteter vorgänge. ZAMM, 3(4):279–289, 1923.
[36] Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms, 7(2):20:1–20:17, 2011. Announced at ICALP’07. doi:10.1145/1921659.1921666.
[37] Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. In STOC, pages 377–388. ACM, 2019. doi:10.1145/3313276.3316381.
[38] Ofer Grossman and Merav Parter. Improved deterministic distributed construction of spanners. In DISC, volume 91 of LIPIcs, pages 24:1–24:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.DISC.2017.24.
[39] Anupam Gupta and Amit Kumar. Online steiner tree with deletions. In SODA, pages 455–467. SIAM, 2014. doi:10.1137/1.9781611973402.34.
[40] Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In SODA, pages 468–479. SIAM, 2014. doi:10.1137/1.9781611973402.35.
[41] Anupam Gupta and Roie Levin. Fully-dynamic submodular cover with bounded recourse. In FOCS, pages 1147–1157. IEEE, 2020. doi:10.1109/FOCS46700.2020.00110.
[42] Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites. Adaptive machine unlearning. In NeurIPS, volume 34. Curran Associates, Inc., 2021.
[43] Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Decremental sssp in weighted digraphs: Faster and against an adaptive adversary. In SODA, pages 2542–2561. SIAM, 2020. doi:10.1137/1.9781611975994.155.
[44] Moritz Hardt and Jonathan R. Ullman. Preventing false discovery in interactive data analysis is hard. In FOCS, pages 454–463. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.55.
[45] Avinatan Hasidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. NeurIPS, 33, 2020.
[46] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In STOC, pages 489–498. ACM, 2016. doi:10.1145/2897518.2897638.
[47] Jacob Holm and Eva Rotenberg. Fully-dynamic planarity testing in polylogarithmic time. In STOC, pages 167–180. ACM, 2020. doi:10.1145/3357713.3384249.
[48] Jacob Holm and Eva Rotenberg. Worst-case polylog incremental SPQR-trees: Embeddings, planarity, and triconnectivity. In Proceedings of the 2020 ACM-SIAM, SODA, pages 2378–2397, 2020. doi:10.1137/1.9781611975994.146.
[49] Piotr Indyk and David Woodruff. Optimal approximations of the frequency moments of data streams. In STOC, pages 202–208. Association for Computing Machinery, 2005. doi:10.1145/1060590.1060621.
[50] Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld. A new analysis of differential privacy’s generalization guarantees. In ITCS, volume 151 of LIPIcs, pages 31:1–31:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ITCS.2020.31.
[51] Alison Hsiang-Hsuan Liu and Jonathan Toole-Charignon. The power of amortized recourse for online graph problems. In Approximation and Online Algorithms, pages 134–153. Springer International Publishing, 2022. doi:10.1007/978-3-031-18367-6_7.
[52] Jelani Nelson, Huy L. Nguyên, and David P. Woodruff. On deterministic sketching and streaming for sparse recovery and norm estimation. In APPROX-RANDOM, volume 7408 of Lecture Notes in Computer Science, pages 627–638. Springer, 2012. doi:10.1007/978-3-642-32512-0_53.
[53] George Pólya. Sur quelques points de la théorie des probabilités. In Annales de l’institut Henri Poincaré, volume 1, pages 117–161, 1930.
[54] Ryan M. Rogers, Aaron Roth, Adam D. Smith, and Om Thakkar. Max-information, differential privacy, and post-selection hypothesis testing. In FOCS, pages 487–494. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.59.
[55] Y. L. Tong. Stochastic orders and their applications (Moshe Shaked and J. George Shanthikumar). SIAM Review, 37(3):477–479, 1995. doi:10.1137/1037117.
[56] David Wajc. Rounding dynamic matchings against an adaptive adversary. In STOC, pages 194–207. Association for Computing Machinery, 2020. doi:10.1145/3357713.3384258.
[57] David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In FOCS, pages 1183–1196. IEEE Computer Society, 2022. doi:10.1109/FOCS52979.2021.00116.

[bib.bib1] [1] Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. In PODS, pages 15–27. ACM, 2022. doi:10.1145/3517804.3526228.

[bib.bib2] [2] N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58:137–147, 1999. doi:10.1006/JCSS.1997.1545.

[bib.bib3] [3] Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. In ITCS, volume 251 of LIPIcs, pages 8:1–8:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ITCS.2023.8.

[bib.bib4] [4] Giorgio Ausiello, Paolo Giulio Franciosa, and Giuseppe F. Italiano. Small stretch spanners on dynamic graphs. J. Graph Algorithms Appl., 10(2):365–385, 2006. Announced at ESA’05. doi:10.7155/JGAA.00133.

[bib.bib5] [5] Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, and Stefan Schmid. Dynamic balanced graph partitioning. SODA, 34(3):1791–1812, 2020. doi:10.1137/17M1158513.

[bib.bib6] [6] Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. In STOC, pages 1046–1059. ACM, 2016. doi:10.1145/2897518.2897566.

[bib.bib7] [7] Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms, 8(4):35:1–35:51, 2012. Announced at SODA’08. doi:10.1145/2344422.2344425.

[bib.bib8] [8] MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In SODA, pages 2677–2727. SIAM, 2023. doi:10.1137/1.9781611977554.CH101.

[bib.bib9] [9] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In FOCS, pages 382–405, 2019. doi:10.1109/FOCS.2019.00032.

[bib.bib10] [10] Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. In SOSA, pages 214–227. SIAM, 2022. doi:10.1137/1.9781611977066.15.

[bib.bib11] [11] Omri Ben-Eliezer, Rajesh Jayaram, David P Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. In PODS, pages 63–80, 2020. doi:10.1145/3375395.3387658.

[bib.bib12] [12] Michael A. Bender, Jake Christensen, Alex Conway, Martin Farach-Colton, Rob Johnson, and Meng-Tsung Tsai. Optimal ball recycling. In SODA, pages 2527–2546. SIAM, 2018.

[bib.bib13] [13] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432, 2020. arXiv:2004.08432.

[bib.bib14] [14] Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. In SODA, pages 1899–1918, 2019. doi:10.1137/1.9781611975482.115.

[bib.bib15] [15] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In ICALP, pages 20:1–20:20, 2022. doi:10.4230/LIPICS.ICALP.2022.20.

[bib.bib16] [16] Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic dynamic matching in O(1) update time. Algorithmica, 82(4):1057–1080, 2020. doi:10.1007/S00453-019-00630-4.

[bib.bib17] [17] Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc. Online edge coloring algorithms via the nibble method. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2830–2842. SIAM, 2021. doi:10.1137/1.9781611976465.168.

[bib.bib18] [18] Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In SODA, pages 785–804. SIAM, 2015. doi:10.1137/1.9781611973730.54.

[bib.bib19] [19] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In STOC, pages 398–411. ACM, 2016. doi:10.1145/2897518.2897568.

[bib.bib20] [20] Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. In ESA, volume 244 of LIPIcs, pages 17:1–17:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.17.

[bib.bib21] [21] Guy Blanc. Subsampling suffices for adaptive data analysis. In STOC, pages 999–1012. ACM, 2023. doi:10.1145/3564246.3585226.

[bib.bib22] [22] Greg Bodwin and Sebastian Krinninger. Fully dynamic spanners with worst-case update time. In ESA, pages 17:1–17:18, 2016. doi:10.4230/LIPIcs.ESA.2016.17.

[bib.bib23] [23] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In NeurIPS, NIPS ’21. Curran Associates Inc., 2021.

[bib.bib24] [24] Daniel G. Brown. How I wasted too long finding a concentration inequality for sums of geometric variables. URL: https://cs.uwaterloo.ca/˜browndg/negbin.pdf.

[bib.bib25] [25] Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 217–226, 2016. doi:10.1145/2933057.2933083.

[bib.bib26] [26] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. Theoretical Computer Science, 312(1):3–15, 2004. Automata, Languages and Programming. doi:10.1016/S0304-3975(03)00400-6.

[bib.bib27] [27] Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In FOCS, pages 370–381, 2019. doi:10.1109/FOCS.2019.00031.

[bib.bib28] [28] Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In NeurIPS, volume 33, pages 11178–11190. Curran Associates, Inc., 2020.

[bib.bib29] [29] Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In SODA, pages 389–400, 2019. doi:10.1145/3313276.3316320.

[bib.bib30] [30] Edith Cohen, Xin Lyu, Jelani Nelson, Tamas Sarlos, Moshe Shechner, and Uri Stemmer. On the robustness of CountSketch to adaptive inputs. In ICML, volume 162, pages 4112–4140. PMLR, 2022. URL: https://proceedings.mlr.press/v162/cohen22a.html.

[bib.bib31] [31] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 4112–4140. PMLR, 2022. URL: https://proceedings.mlr.press/v162/cohen22a.html.

[bib.bib32] [32] Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58–75, 2005. doi:10.1016/j.jalgor.2003.12.001.

[bib.bib33] [33] Jimmy Z. Di, Jack Douglas, Jayadev Acharya, Gautam Kamath, and Ayush Sekhari. Hidden poison: Machine unlearning enables camouflaged poisoning attacks. In NeurIPS ML Safety Workshop, 2022. URL: https://openreview.net/forum?id=zml9gDnulI9.

[bib.bib34] [34] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In NIPS, pages 2350–2358, 2015. URL: https://proceedings.neurips.cc/paper/2015/hash/bad5f33780c42f2588878a9d07405083-Abstract.html.

[bib.bib35] [35] Florian Eggenberger and George Pólya. Über die statistik verketteter vorgänge. ZAMM, 3(4):279–289, 1923.

[bib.bib36] [36] Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms, 7(2):20:1–20:17, 2011. Announced at ICALP’07. doi:10.1145/1921659.1921666.

[bib.bib37] [37] Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. In STOC, pages 377–388. ACM, 2019. doi:10.1145/3313276.3316381.

[bib.bib38] [38] Ofer Grossman and Merav Parter. Improved deterministic distributed construction of spanners. In DISC, volume 91 of LIPIcs, pages 24:1–24:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.DISC.2017.24.

[bib.bib39] [39] Anupam Gupta and Amit Kumar. Online steiner tree with deletions. In SODA, pages 455–467. SIAM, 2014. doi:10.1137/1.9781611973402.34.

[bib.bib40] [40] Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In SODA, pages 468–479. SIAM, 2014. doi:10.1137/1.9781611973402.35.

[bib.bib41] [41] Anupam Gupta and Roie Levin. Fully-dynamic submodular cover with bounded recourse. In FOCS, pages 1147–1157. IEEE, 2020. doi:10.1109/FOCS46700.2020.00110.

[bib.bib42] [42] Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites. Adaptive machine unlearning. In NeurIPS, volume 34. Curran Associates, Inc., 2021.

[bib.bib43] [43] Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Decremental sssp in weighted digraphs: Faster and against an adaptive adversary. In SODA, pages 2542–2561. SIAM, 2020. doi:10.1137/1.9781611975994.155.

[bib.bib44] [44] Moritz Hardt and Jonathan R. Ullman. Preventing false discovery in interactive data analysis is hard. In FOCS, pages 454–463. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.55.

[bib.bib45] [45] Avinatan Hasidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. NeurIPS, 33, 2020.

[bib.bib46] [46] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In STOC, pages 489–498. ACM, 2016. doi:10.1145/2897518.2897638.

[bib.bib47] [47] Jacob Holm and Eva Rotenberg. Fully-dynamic planarity testing in polylogarithmic time. In STOC, pages 167–180. ACM, 2020. doi:10.1145/3357713.3384249.

[bib.bib48] [48] Jacob Holm and Eva Rotenberg. Worst-case polylog incremental SPQR-trees: Embeddings, planarity, and triconnectivity. In Proceedings of the 2020 ACM-SIAM, SODA, pages 2378–2397, 2020. doi:10.1137/1.9781611975994.146.

[bib.bib49] [49] Piotr Indyk and David Woodruff. Optimal approximations of the frequency moments of data streams. In STOC, pages 202–208. Association for Computing Machinery, 2005. doi:10.1145/1060590.1060621.

[bib.bib50] [50] Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld. A new analysis of differential privacy’s generalization guarantees. In ITCS, volume 151 of LIPIcs, pages 31:1–31:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ITCS.2020.31.

[bib.bib51] [51] Alison Hsiang-Hsuan Liu and Jonathan Toole-Charignon. The power of amortized recourse for online graph problems. In Approximation and Online Algorithms, pages 134–153. Springer International Publishing, 2022. doi:10.1007/978-3-031-18367-6_7.

[bib.bib52] [52] Jelani Nelson, Huy L. Nguyên, and David P. Woodruff. On deterministic sketching and streaming for sparse recovery and norm estimation. In APPROX-RANDOM, volume 7408 of Lecture Notes in Computer Science, pages 627–638. Springer, 2012. doi:10.1007/978-3-642-32512-0_53.

[bib.bib53] [53] George Pólya. Sur quelques points de la théorie des probabilités. In Annales de l’institut Henri Poincaré, volume 1, pages 117–161, 1930.

[bib.bib54] [54] Ryan M. Rogers, Aaron Roth, Adam D. Smith, and Om Thakkar. Max-information, differential privacy, and post-selection hypothesis testing. In FOCS, pages 487–494. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.59.

[bib.bib55] [55] Y. L. Tong. Stochastic orders and their applications (Moshe Shaked and J. George Shanthikumar). SIAM Review, 37(3):477–479, 1995. doi:10.1137/1037117.

[bib.bib56] [56] David Wajc. Rounding dynamic matchings against an adaptive adversary. In STOC, pages 194–207. Association for Computing Machinery, 2020. doi:10.1145/3357713.3384258.

[bib.bib57] [57] David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In FOCS, pages 1183–1196. IEEE Computer Society, 2022. doi:10.1109/FOCS52979.2021.00116.

Minimizing Recourse in an Adaptive Balls and Bins Game

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our results

(1) Load balancing Games.

(2) 𝟑-spanner with small recourse.

Additional games and related questions

2 Balls and Bins, Deletion Against An Adaptive Adversary

Theorem 1 (Main theorem).

Theorem 2.

Definition 3 (Phase).

Definition 4 (First-order stochastic dominance).

Lemma 5.

Proof.

Base case (𝒖=𝟎).

Inductive step.

Theorem 6 ([55]).

Theorem 7 ([24]).

Proof of Theorem 2.

Proof of Theorem 1.

3 Decremental Load Balancing Framework

Theorem 8 (Main theorem).

Theorem 9.

Theorem 10.

Definition 11 (Phases).

Lemma 12.

Proof.

Lemma 13.

Proof.

Base case (𝒖=𝟎).

Inductive step.

Proof of Theorem 10.

Proof of Theorem 9.

4 Fully Dynamic 3-Spanner Against Adaptive Adversary

Theorem 14.

4.1 Algorithm Description

Static Construction

Claim 15.

Proof.

Dynamic Maintenance

Maintaining 𝑬𝟏 and 𝑬𝟐

Maintaining 𝑬𝟑: Deletions vs. Insertions

Deletions in 𝑬𝟑

Lemma 16.

Proof of Lemma 16.

Epoch Initialization

Amortize Initialization to Worst-Case

5 Concluding remarks

References

(2) $3$ -spanner with small recourse.

Base case ( $u=0$ ).

Base case ( $u=0$ ).

Maintaining $E_{1}$ and $E_{2}$

Maintaining $E_{3}$ : Deletions vs. Insertions

Deletions in $E_{3}$