A tail bound for read-kfamilies of functions

DOI10.1002/rsa.20532zbMath1338.60082arXiv1205.1478OpenAlexW2158343516MaRDI QIDQ3192374

Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan, Michael E. Saks

Publication date: 12 October 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.1478

zbMATH Keywords

information theoryShearer's lemmalimited independenceChernoff-like large deviation bound

Mathematics Subject Classification ID

Large deviations (60F10)

Related Items (6)

Joint Alignment from Pairwise Differences with a Noisy Oracle ⋮ Extremal bipartite independence number and balanced coloring ⋮ Hoeffding's inequality for sums of dependent random variables ⋮ Hölder-type inequalities and their applications to concentration and correlation bounds ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Hitting times for Shamir’s problem

Cites Work

• Applications of Stein's method for concentration inequalities
• Quasi-random graphs and graph limits
• Some intersection theorems for ordered sets and graphs
• A generalization of Hölder's inequality and some probability inequalities
• Concentration inequalities using the entropy method
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• On Talagrand's deviation inequalities for product measures
• Hypergraphs, Entropy, and Inequalities
• Large deviations for sums of partly dependent random variables
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: A tail bound for read-kfamilies of functions