Maintaining Random Assignments under Adversarial Dynamics
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914451629801472 |
|---|---|
| author | Haeupler, Bernhard Paramonov, Anton |
| author_facet | Haeupler, Bernhard Paramonov, Anton |
| contents | We study and further develop powerful general-purpose schemes to maintain random assignments under adversarial dynamic changes.
The goal is to maintain assignments that are (approximately) distributed similarly as a completely fresh resampling of all assignments after each change, while doing only a few resamples per change. This becomes particularly interesting and challenging when dynamics are controlled by an adaptive adversary.
Our work builds on and further develops the proactive resampling technique [Bhattacharya, Saranurak, and Sukprasert ESA'22]. We identify a new ``temporal selection'' attack that adaptive adversaries can use to cause biases, even against proactive resampling. We propose a new ''temporal aggregation'' principle that algorithms should follow to counteract these biases, and present two powerful new resampling schemes based on this principle.
We give various applications of our new methods. The main one in maintaining proper coloring of the graph under adaptive adversarial modifications: we maintain $O(Δ)$ coloring for general graphs with maximum degree $Δ$ and $O(\fracΔ{\ln Δ})$ coloring for triangle free graphs, both with sublinear in the number of vertices average work per modification. Other applications include efficiently maintaining random walks in dynamically changing graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05606 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Maintaining Random Assignments under Adversarial Dynamics Haeupler, Bernhard Paramonov, Anton Data Structures and Algorithms We study and further develop powerful general-purpose schemes to maintain random assignments under adversarial dynamic changes. The goal is to maintain assignments that are (approximately) distributed similarly as a completely fresh resampling of all assignments after each change, while doing only a few resamples per change. This becomes particularly interesting and challenging when dynamics are controlled by an adaptive adversary. Our work builds on and further develops the proactive resampling technique [Bhattacharya, Saranurak, and Sukprasert ESA'22]. We identify a new ``temporal selection'' attack that adaptive adversaries can use to cause biases, even against proactive resampling. We propose a new ''temporal aggregation'' principle that algorithms should follow to counteract these biases, and present two powerful new resampling schemes based on this principle. We give various applications of our new methods. The main one in maintaining proper coloring of the graph under adaptive adversarial modifications: we maintain $O(Δ)$ coloring for general graphs with maximum degree $Δ$ and $O(\fracΔ{\ln Δ})$ coloring for triangle free graphs, both with sublinear in the number of vertices average work per modification. Other applications include efficiently maintaining random walks in dynamically changing graphs. |
| title | Maintaining Random Assignments under Adversarial Dynamics |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.05606 |