Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems

Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak · 2025

Read Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems by Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20341.txt.

Introduction

Aaron Bernstein and four co-authors prove the first time gap between two kinds of foes in dynamic graph work. One foe sets the full update list in advance. The other picks each step by what it sees. Past gaps of this kind used fake tasks or strong crypto claims. Here the tasks are plain graph tasks, and the claims rest on known fine-grained bounds.

For one task on max free sets, each fast step method that faces the live foe needs near-linear time per step. Yet polylog time works when the foe is fixed in advance. The same split holds for a clique task. Known live-foe methods match the new floor, so the gap is now closed and vast.

Catalog record

CREATORAaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20341

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak Abstract We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, based on popular fine-grained complexity hypotheses. Specifically, under the combinatorial BMM hypothesis, we show that every combinatorial algorithm against an adaptive adversary for the incremental maximal independent set problem requires n 1 − o ⁡ ( 1 ) n^{1-o(1)} amortized update time. Furthermore, assuming either the 3SUM or APSP hypotheses, every algorithm for the decremental maximal clique problem needs Δ / n o ⁡ ( 1 ) \Delta/n^{o(1)} amortized update time when the initial maximum degree is Δ ≤ n \Delta\leq\sqrt{n} . These lower bounds are matched by existing algorithms against adaptive adversaries. In contrast, both problems admit algorithms against oblivious adversaries that achieve polylog ⁡ ( n ) \operatorname{polylog}(n) amortized update time [ BDH+19 , CZ19 ] . Therefore, our separations are exponential. Previously known separations for dynamic algorithms were either engineered for contrived problems and relied on strong cryptographic assumptions [ BKM+22 ] , or worked for problems whose inputs are not explicitly given but are accessed through oracle calls [ BEF+23 ] . As a byproduct, we also provide a separation between incremental and decremental algorithms for the triangle detection problem: we show a decremental algorithm with O ~ ​ ( n ω ) \tilde{O}(n^{\omega}) total update time, while every incremental algorithm requires n 3 − o ⁡ ( 1 ) n^{3-o(1)} total update time, assuming the OMv hypothesis. To our knowledge this is the first separation of this kind. 1 Introduction In the setting of dynamic algorithms, an adversary generates a sequence of updates to the input, and a dynamic algorithm aims to maintain useful information about the input throughout the updates with minimal update time. The adversary is oblivious if its update sequence is fixed from the beginning and, in particular, is independent of the algorithm’s output. Otherwise, the adversary is adaptive if the next update can be adaptively chosen based on the algorithm’s previous outputs. An algorithm is robust or works against an adaptive adversary if its performance is guaranteed even against an adaptive adversary. Otherwise, if it only works against an oblivious adversary, it is called non-robust . Robustness against adaptive adversaries is needed in a wide range of real-world applications and is well-studied across many areas of computer sciences, such as streaming algorithms [ BJWY22 , HKM+22 , ACGS23 ] , online algorithms [ BBK+94 ] , and adaptive data analysis [ DFH+15 , HU14 ] . Robustness is especially critical for dynamic algorithms as it enables their use as subroutines in static algorithms, which is a key application of dynamic algorithms. Success in Making Algorithms Robust. For many dynamic graph problems, the first efficient algorithms were non-robust, with robust algorithms lagging far behind. But while many gaps remain, in the past decade, we have witnessed many successful lines of work on developing robust dynamic algorithms that match the near-optimal guarantees of the non-robust ones [ RZ08 , KKM13 , BKS12 , HKN18 , ADK+16 , Che18 , BGW19 ] . This includes robust algorithms for spanning forests [ NS17 , Wul17 , NSW17 , CGL+20 , GRST21 ] , approximate shortest paths [ BC16 , BC17 , Chu21 , CS21 , BGS21 , CZ23 , HLS24 ] , graph sparsifiers [ CGH+20 , BvdBG+22 , BSS22 , KMG24 ] , and reachability [ BGS20 , CKL+24 , vdBCK+24 ] . These data structures and their techniques have been the core powerhouse behind breakthroughs in static algorithms, including almost-linear time algorithms for min-cost flow [ CKL+25 , vdBCP+23 ] and Gomory-Hu trees [ AKL+22 , ALPS23 ] . Recently, another significant barrier was overcome for symmetry-breaking problems, which include maximal independent set, maximal matching, and (\Delta+1) -vertex coloring. These problems admit near-optimal non-robust algorithms with polylogarithmic update time [ BGS18 , BCHN18 , CZ19 , BDH+19 ] , but no robust algorithms with o(n) update time were previously known. This past year, however, [ BRW25 ] and [ BBKS25 ] introduced new robust dynamic algorithms with truly sublinear n^{1-\Omega(1)} update times for (\Delta+1) -vertex coloring and maximal matching, respectively. Given these positive evidences over the years, can we hope to always almost match the performance of non-robust algorithms with robust ones? Previous Separations. Strictly speaking, the answer is no. Consider this artificial problem. Initially, we are given an array A=[A_{1},\dots,A_{n}] of n numbers. For each update, the adversary chooses an index i\in[n] and marks it as deleted. The goal is to maintain a tuple (i,A_{i}) where i is not yet deleted, if it exists. Observe that an adaptive adversary can force every algorithm to update its answers n times by deleting i whenever (i,A_{i}) is outputted. But, assuming an oblivious adversary, if we maintain (i,A_{i}) where i is a random undeleted index, then our maintained index i will be deleted at most O(\log n) times in total with high probability. Thus, only O(\log n) entries need to be queried. Therefore, if the input array is provided as an oracle, it is quite simple to achieve an exponential separation between oblivious and adaptive adversaries. The above separation, however, has two drawbacks: 1. The problem is artificial, and 2. The input must be prepared as an oracle. This model does not capture most standard dynamic problems. Regarding the second drawback, note that the above O(\log n) -time algorithm cannot even read the entire input. In contrast, in most dynamic graph, string, and geometric problems, the input and updates are given explicitly, requiring every algorithm to spend at least linear time to read the input. Unfortunately, all known separations for dynamic algorithms still suffer from one of the above drawbacks. Specifically, the separations by Beimal et al. [ BKM+22 ] were engineered for artificial problems, one of them similar to the example above, and also assumed strong cryptographic assumptions. Another separation by Bateni et al. [ BEF+23 ] was for dynamic k -clustering problems which assume an oracle for the input and are hence not using the standard measure of update time. Furthermore, their lower bound only applies to deterministic algorithms and does not strictly separate robust from non-robust algorithms. 1 1 1 The adversary in the lower bound of [ BEF+23 ] is metric-adaptive and, so it cannot capture most randomized k -clustering algorithms even in the static setting (see, e.g., [ MP04 ] ) which assume a weaker point-adaptive adversary. The robust randomized algorithm by [ BCF25 ] beats the lower bound of [ BEF+23 ] because of this. Until now, there is no oblivious-vs-adaptive separation for natural dynamic problems with explicit input. 1.1 Our Results: Natural Oblivious-vs-Adaptive Separations We establish the first update-time separations between non-robust and robust dynamic algorithms for natural dynamic problems with explicit input, assuming popular fine-grained complexity hypotheses, detailed in Section 2 . Recall that incremental (decremental) graphs are graphs undergoing only edge insertions (deletions). Incremental MIS. Our first separation is for the dynamic maximal independent set (MIS) problem [ AOSS18 , AOSS19 , BDH+19 , CZ19 , GK21 ] . In this problem,

Read the complete text