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

(32)

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

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)