Image de couverture de livre

The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kuszmaul, William, Qi, Qi
Format:	Preprint
Publié:	2021
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

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
par: Kuszmaul, William
Publié: (2025)

Scheduling Jobs with Work-Inefficient Parallel Solutions
par: Kuszmaul, William, et autres
Publié: (2024)

Tight Analyses of Ordered and Unordered Linear Probing
par: Braverman, Mark, et autres
Publié: (2025)

Efficient $d$-ary Cuckoo Hashing at High Load Factors by Bubbling Up
par: Kuszmaul, William, et autres
Publié: (2025)

Fingerprint Filters Are Optimal
par: Kuszmaul, William, et autres
Publié: (2025)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
par: Kuszmaul, William, et autres
Publié: (2025)

Optimal Non-Oblivious Open Addressing
par: Bender, Michael A., et autres
Publié: (2025)

Tight Bounds for Classical Open Addressing
par: Bender, Michael A., et autres
Publié: (2024)

A Nearly Quadratic Improvement for Memory Reallocation
par: Farach-Colton, Martin, et autres
Publié: (2024)

History-Independent Load Balancing
par: Bender, Michael A., et autres
Publié: (2026)

Optimal Bounds for Open Addressing Without Reordering
par: Farach-Colton, Martin, et autres
Publié: (2025)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
par: Kuszmaul, William, et autres
Publié: (2024)

Layered List Labeling
par: Bender, Michael A., et autres
Publié: (2024)

Static Retrieval Revisited: To Optimality and Beyond
par: Hu, Yang, et autres
Publié: (2025)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
par: Kirkpatrick, Yael, et autres
Publié: (2026)

Nearly Optimal List Labeling
par: Bender, Michael A., et autres
Publié: (2024)

Finding 4-Additive Spanners: Faster, Stronger, and Simpler
par: Qi, Chuhan
Publié: (2025)

Lookback Prophet Inequalities
par: Benomar, Ziyad, et autres
Publié: (2024)

Combinatorial Philosopher Inequalities
par: Sun, Enze, et autres
Publié: (2025)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
par: Gawrychowski, Paweł, et autres
Publié: (2024)

Prophet Inequalities over Time
par: Abels, Andreas, et autres
Publié: (2022)

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
par: Koo, Jaehyun
Publié: (2024)

Sample-Based Matroid Prophet Inequalities
par: Fu, Hu, et autres
Publié: (2024)

The Bichromatic Two-Center Problem on Graphs
par: Sun, Qi, et autres
Publié: (2025)

New Prophet Inequalities via Poissonization and Sharding
par: Harb, Elfarouk
Publié: (2023)

Anytime Sorting Algorithms (Extended Version)
par: Caizergues, Emma, et autres
Publié: (2024)

Strengths and Limitations of Greedy in Cup Games
par: Jasińska, Kalina, et autres
Publié: (2026)

Separating $k$-Median from the Supplier Version
par: Anand, Aditya, et autres
Publié: (2024)

A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
par: Alon, Noga, et autres
Publié: (2024)

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

Pairwise-Independent Contention Resolution
par: Gupta, Anupam, et autres
Publié: (2024)

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
par: Jain, Sanjay, et autres
Publié: (2026)

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
par: Kulik, Ariel, et autres
Publié: (2019)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
par: Jin, Ce, et autres
Publié: (2024)

Deep Learning Service for Efficient Data Distribution Aware Sorting
par: Zhu, Xiaoke, et autres
Publié: (2019)

Optimal Protocols for 2-Party Contention Resolution
par: Wang, Dingyu
Publié: (2024)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
par: Jansen, Klaus, et autres
Publié: (2024)

Efficient Stochastic Routing in Path-Centric Uncertain Road Networks -- Extended Version
par: Guo, Chenjuan, et autres
Publié: (2024)

Matrix Multiplication Reductions
par: Gola, Ashish, et autres
Publié: (2024)

Threshold Rules for the Classical Prophet Inequality
par: Zhang, Jiechen
Publié: (2026)