Leveraging parameterized Chernoff bounds for simplified algorithm analyses

DOI10.1016/J.IPL.2024.106516MaRDI QIDQ6602327zbMATH OpenFDO

Authors Michael B. Dillencourt, Michael T. Goodrich, Michael Mitzenmacher

Publication date 11 September 2024

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106516

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• scientific article; zbMATH DE number 437558
• A guided tour of Chernoff bounds
• Probabilistic recurrence relations revisited
• Concentration of Measure for the Analysis of Randomized Algorithms

Cites work

• scientific article; zbMATH DE number 1253984 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Scheme for Fast Parallel Communication
• A guided tour of Chernoff bounds
• A note on the height of binary search trees
• A probabilistic analysis of the Floyd–Rivest expected time selection algorithm
• An overview of the theory of large deviations and applications to statistical mechanics
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Expected time bounds for selection
• New approximations to the principal real-valued branch of the Lambert W-function
• On Floyd and Rivest's SELECT algorithm
• On the Lambert \(w\) function
• On the runtime and robustness of randomized broadcasting
• Probability Inequalities for Sums of Bounded Random Variables
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Real values of the W -function
• Simplified Chernoff bounds with powers-of-two probabilities
• The height of a random binary search tree
• The probabilistic method

This page was built for publication: Leveraging parameterized Chernoff bounds for simplified algorithm analyses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6602327)