Pith. sign in

REVIEW 6 cited by

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2102.05077 v2 pith:6LWPUXKC submitted 2021-02-09 cs.DS

William Kuszmaul , Qi Qi This is my paper · ORCID
classification cs.DS
keywords inequalityazumaboundsanalysischernoffcontentiongeneralizationmultiplicative
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

Azuma's inequality is a tool for proving concentration bounds on random variables. The inequality can be thought of as a natural generalization of additive Chernoff bounds. On the other hand, the analogous generalization of multiplicative Chernoff bounds does not appear to be widely known. We formulate a multiplicative-error version of Azuma's inequality. We then show how to apply this new inequality in order to greatly simplify (and correct) the analysis of contention delays in multithreaded systems managed by randomized work stealing.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Subcubic Coin Tossing in Asynchrony without PKI

    cs.DC 2026-03 accept novelty 8.0 of 10

    A committee-based transformation gives setup-free asynchronous common coins with O~(n^2.5) (perfect) and O~(n^{7/3}) (hash-based) communication against Θ(n) adaptive byzantine faults.

  2. Tight Analyses of Ordered and Unordered Linear Probing

    cs.DS 2025-01 accept novelty 8.0 of 10

    Linear probing with tombstones has amortized expected insertion time Θ(x log^{1.5} x), with matching upper and lower bounds, resolving the open gap from FOCS 2021.

  3. Paths and Intersections: Minimum Realization of Okamura-Seymour Instances

    cs.DS 2026-07 accept novelty 7.0 of 10

    Every OS metric has a unique minimum-crossing medial template; its primal arrangements are precisely the fewest-edge disk realizations, recoverable with realizing lengths in polynomial time.

  4. Fast Concurrent Primitives Despite Contention

    cs.DS 2026-04 unverdicted novelty 7.0 of 10

    Under a roughly-synchronous stochastic scheduler, O(1) hardware registers (plus one CAS) implement contention-tolerant R/W and CAS objects with O(log P) latency w.h.p., with a matching space-latency lower bound.

  5. Faster Dynamic $(\Delta+1)$-Coloring Against Adaptive Adversaries

    cs.DS 2025-04 conditional novelty 7.0 of 10

    A randomized dynamic algorithm maintains a proper (Δ+1)-coloring against adaptive adversaries in Õ(n^{2/3}) amortized update time, improving the prior Õ(n^{8/9}) bound.

  6. Validity and efficiency of the conformal CUSUM procedure

    math.ST 2024-12 conditional novelty 7.0 of 10

    Conformal CUSUM can be tuned so its pre-change statistics match the ideal likelihood-ratio CUSUM exactly, giving controlled false alarms under exchangeability alone.

Pith tools