Cover Image

Chasing Small Sets Optimally Against Adaptive Adversaries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Coester, Christian, Tudose, Alexa
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Transposition is Nearly Optimal for IID List Update
by: Coester, Christian
Published: (2026)

Online Monotone Metric Embeddings
by: Coester, Christian, et al.
Published: (2026)

Randomized $k$-server in polynomial time
by: Coester, Christian, et al.
Published: (2026)

Smoothed Analysis of Online Metric Problems
by: Coester, Christian, et al.
Published: (2025)

Online 3-Taxi on General Metrics
by: Coester, Christian, et al.
Published: (2025)

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
by: Bai, Xingjian, et al.
Published: (2024)

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
by: Flin, Maxime, et al.
Published: (2025)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
by: Behnezhad, Soheil, et al.
Published: (2024)

Learning-Augmented Priority Queues
by: Benomar, Ziyad, et al.
Published: (2024)

Chasing Positive Bodies
by: Bhattacharya, Sayan, et al.
Published: (2023)

Optimal Neighborhood Exploration for Dynamic Independent Sets
by: Borowitz, Jannick, et al.
Published: (2024)

Robust Streaming Against Low-Memory Adversaries
by: Ben-Eliezer, Omri, et al.
Published: (2025)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
by: Buchbinder, Niv, et al.
Published: (2025)

Time-Optimal Construction of String Synchronizing Sets
by: Ellert, Jonas, et al.
Published: (2026)

Optimal Testing of Reed-Muller Codes with an Online Adversary
by: Kelman, Esty, et al.
Published: (2026)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
by: Gribelyuk, Elena, et al.
Published: (2025)

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
by: Banihashem, Kiarash, et al.
Published: (2025)

Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
by: Cruciani, Emilio, et al.
Published: (2025)

The Role of Dimension in the Online Chasing Problem
by: Papazov, Hristo
Published: (2023)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
by: Navarro, Gonzalo
Published: (2024)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
by: Bernstein, Aaron, et al.
Published: (2025)

Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds
by: Dürr, Christoph, et al.
Published: (2024)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
by: Larsen, Kasper Green, et al.
Published: (2023)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

Chasing Convex Functions with Long-term Constraints
by: Lechowicz, Adam, et al.
Published: (2024)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
by: Gorbachev, Egor, et al.
Published: (2024)

Grafite: Taming Adversarial Queries with Optimal Range Filters
by: Costa, Marco, et al.
Published: (2023)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
by: Nadimpalli, Shivam, et al.
Published: (2024)

Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2025)

Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
by: Udwani, Rajan
Published: (2024)

Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2023)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
by: Großmann, Ernestine, et al.
Published: (2026)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
by: Grilnberger, Mara, et al.
Published: (2026)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2026)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
by: Großmann, Ernestine, et al.
Published: (2024)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
by: Chhabra, Adil, et al.
Published: (2025)

Compressed Set Representations based on Set Difference
by: Gagie, Travis, et al.
Published: (2026)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

Suffixient Sets
by: Depuydt, Lore, et al.
Published: (2023)

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
by: Chandrasekaran, Karthekeyan, et al.
Published: (2023)