Constructive Proofs of Concentration Bounds
From MaRDI portal
Publication:3588439
DOI10.1007/978-3-642-15369-3_46zbMath1305.68331OpenAlexW1559980198MaRDI QIDQ3588439
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
Related Items (22)
Locally computable UOWHF with linear shrinkage ⋮ 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 ⋮ Hoeffding's inequality for sums of dependent random variables ⋮ On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing ⋮ Better security-efficiency trade-offs in permutation-based two-party computation ⋮ 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 ⋮ Limitations of current wireless link scheduling algorithms ⋮ Unifying presampling via concentration bounds ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Improved direct product theorems for randomized query complexity ⋮ Survey on nonlocal games and operator space theory ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Basic Facts about Expander Graphs ⋮ A constructive proof of a concentration bound for real-valued random variables ⋮ Discordant voting protocols for cyclically linked agents ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem ⋮ Time-space tradeoffs and short collisions in Merkle-Damgård hash functions ⋮ Local correctability of expander codes
This page was built for publication: Constructive Proofs of Concentration Bounds
