Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems

Society for Industrial and Applied Mathematics eBooks 2026

View at publisher
Authors: Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Péter Kiss, Thatchaphol Saranurak
DOI: 10.1137/1.9781611978971.202
Cited by: 0

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.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Graph Theory and Algorithms

Publication details

Journal / source
Society for Industrial and Applied Mathematics eBooks
Pages
5669–5687
Publication date
1 January 2026
Language
EN