Image de couverture de livre

On the Adversarial Robustness of Online Importance Sampling

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kenneth-Mordoch, Yotam, Sapir, Shay
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Faster Pseudo-Deterministic Minimum Cut
par: Kenneth-Mordoch, Yotam
Publié: (2026)

Simple Algorithms for Fully Dynamic Edge Connectivity
par: Kenneth-Mordoch, Yotam, et autres
Publié: (2025)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
par: Kenneth-Mordoch, Yotam, et autres
Publié: (2025)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
par: Kenneth-Mordoch, Yotam, et autres
Publié: (2025)

Cut-Query Algorithms with Few Rounds
par: Kenneth-Mordoch, Yotam, et autres
Publié: (2025)

Connectivity Labeling in Faulty Colored Graphs
par: Petruschka, Asaf, et autres
Publié: (2024)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
par: Parter, Merav, et autres
Publié: (2024)

Moderate Dimension Reduction for $k$-Center Clustering
par: Jiang, Shaofeng H. -C., et autres
Publié: (2023)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
par: Kenneth, Yotam, et autres
Publié: (2023)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
par: Jiang, Shaofeng H. -C., et autres
Publié: (2025)

The Power of Recursive Embeddings for $\ell_p$ Metrics
par: Krauthgamer, Robert, et autres
Publié: (2025)

$L_p$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness
par: Lin, Honghao, et autres
Publié: (2025)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
par: Roditty, Liam, et autres
Publié: (2025)

Online versus Offline Adversaries in Property Testing
par: Kelman, Esty, et autres
Publié: (2024)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
par: Boneh, Itai, et autres
Publié: (2025)

Dynamic Set Cover with Worst-Case Recourse
par: Solomon, Shay, et autres
Publié: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
par: Solomon, Shay, et autres
Publié: (2023)

Distances in Planar Graphs are Almost for Free!
par: Mozes, Shay, et autres
Publié: (2026)

Adversarial Resilience in Sequential Prediction via Abstention
par: Goel, Surbhi, et autres
Publié: (2023)

Adversarial Robustness on Insertion-Deletion Streams
par: Gribelyuk, Elena, et autres
Publié: (2026)

Optimal Testing of Reed-Muller Codes with an Online Adversary
par: Kelman, Esty, et autres
Publié: (2026)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
par: Gao, Jie, et autres
Publié: (2025)

Robust Streaming Against Low-Memory Adversaries
par: Ben-Eliezer, Omri, et autres
Publié: (2025)

Online Sampling and Decision Making with Low Entropy
par: Hajiaghayi, Mohammad Taghi, et autres
Publié: (2021)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
par: Gribelyuk, Elena, et autres
Publié: (2025)

Private List Learnability vs. Online List Learnability
par: Hanneke, Steve, et autres
Publié: (2025)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
par: Boneh, Itai, et autres
Publié: (2025)

A Lossless Deamortization for Dynamic Greedy Set Cover
par: Solomon, Shay, et autres
Publié: (2024)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
par: Bukov, Anton, et autres
Publié: (2023)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
par: Woodruff, David P., et autres
Publié: (2024)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
par: Andoni, Alexandr, et autres
Publié: (2026)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
par: Braverman, Mark, et autres
Publié: (2024)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
par: Gribelyuk, Elena, et autres
Publié: (2024)

Tree-Like Shortcuttings of Trees
par: Le, Hung, et autres
Publié: (2025)

Hamming Distance Oracle
par: Boneh, Itai, et autres
Publié: (2024)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
par: Bhattacharya, Sayan, et autres
Publié: (2024)

Arboricity-Dependent Algorithms for Edge Coloring
par: Bhattacharya, Sayan, et autres
Publié: (2023)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
par: Bhattacharya, Sayan, et autres
Publié: (2023)

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
par: Li, Yingxi, et autres
Publié: (2025)

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
par: Roditty, Liam, et autres
Publié: (2026)