Constructive proofs of concentration bounds

DOI10.1007/978-3-642-15369-3_46MaRDI QIDQ3588439zbMATH OpenOpenAlexFDO

Authors Russell Impagliazzo, Valentine Kabanets

Publication date 10 September 2010

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15369-3_46

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Randomized algorithms (68W20)

Recommendations

• A constructive proof of a concentration bound for real-valued random variables
• scientific article
• scientific article; zbMATH DE number 1857648
• A guided tour of Chernoff bounds
• scientific article; zbMATH DE number 437558

Cited in

(34)

• Hoeffding's inequality for sums of dependent random variables
• Time-space tradeoffs and short collisions in Merkle-Damgård hash functions
• Limitations of current wireless link scheduling algorithms
• A constructive proof of a concentration bound for real-valued random variables
• Discordant voting protocols for cyclically linked agents
• Local correctability of expander codes
• Locally computable UOWHF with linear shrinkage
• Unifying presampling via concentration bounds
• Survey on nonlocal games and operator space theory
• Basic Facts about Expander Graphs
• Tight bounds for single-pass streaming complexity of the set cover problem
• A quadratic size-hierarchy theorem for small-depth multilinear formulas
• Sampling lower bounds: Boolean average-case and permutations
• Concentration for limited independence via inequalities for the elementary symmetric polynomials
• Optimal security for keyed hash functions: avoiding time-space tradeoffs for finding collisions
• On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
• Better security-efficiency trade-offs in permutation-based two-party computation
• On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
• Time-space lower bounds for finding collisions in Merkle-Damgård hash functions
• Time-space lower bounds for finding collisions in Merkle-Damgård Hash functions
• Distributed PageRank computation with improved round complexities
• Defective coloring of hypergraphs
• On time-space lower bounds for finding short collisions in sponge hash functions
• Tight characterizations for preprocessing against cryptographic salting
• Towards an understanding of polynomial calculus: new separations and lower bounds
• Time-space tradeoffs for finding multi-collisions in Merkle-Damgård hash functions
• A randomized method for handling a difficult function in a convex optimization problem, motivated by probabilistic programming
• Dynamic maximal matching in clique networks
• Improved direct product theorems for randomized query complexity
• Polynomial lower bound on the effective resistance for the one-dimensional critical long-range percolation
• Better boosting of communication oracles, or not
• Expander Graphs
• Negatively Associated Random Variables
• A guided tour of Chernoff bounds

This page was built for publication: Constructive proofs of concentration bounds

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