Chernoff–Hoeffding Bounds for Applications with Limited Independence

DOI10.1137/S089548019223872XzbMath0819.60032MaRDI QIDQ4837650

Aravind Srinivasan, Jeanette P. Schmidt, Alan R. Siegel

Publication date: 3 July 1995

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

correlation inequalities large deviations randomized algorithms derandomization Chernoff-Hoeffding bounds deterministic simulation limited independence

Mathematics Subject Classification ID

Multivariate distribution of statistics (62H10) Inequalities; stochastic orderings (60E15) Sums of independent random variables; random walks (60G50) Factorials, binomial coefficients, combinatorial functions (05A10) Combinatorial probability (60C05) Large deviations (60F10) Discrete mathematics in relation to computer science (68R99) Theory of computing (68Q99)

Related Items

On the approximability of clique and related maximization problems, Nearly-perfect hypergraph packing is in NC, Dynamic dictionaries for multisets and counting filters with constant time operations, Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence, On the Bernstein-Hoeffding method, Fooling Polytopes, A Framework for Adversarially Robust Streaming Algorithms, A study on several combination problems of classic shop scheduling and shortest path, Pseudorandomness via the Discrete Fourier Transform, Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms, Competitive throughput in multi-hop wireless networks despite adaptive jamming, Approximation algorithms for multiprocessor scheduling under uncertainty, Derandomizing local distributed algorithms under bandwidth restrictions, Deterministic Massively Parallel Connectivity, Algorithms and lower bounds for comparator circuits from shrinkage, The number of rational points of hyperelliptic curves over subsets of finite fields, Hoeffding's inequality for sums of dependent random variables, Unnamed Item, Tight Probability Bounds with Pairwise Independence, Distributed Symmetry Breaking on Power Graphs via Sparsification, A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints, Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs, Sketching asynchronous data streams over sliding windows, Cache-oblivious hashing, Optimal Hashing in External Memory, Dynamic dictionaries for multisets and counting filters with constant time operations, Improved parallel approximation of a class of integer programming problems, Hölder-type inequalities and their applications to concentration and correlation bounds, Collaborate with strangers to find own preferences, Cost-sharing mechanisms for network design, Maximizing Throughput in Flow Shop Real-Time Scheduling, How good is a dense shop schedule?, A note on the distribution of the number of prime factors of the integers, Meet and merge: approximation algorithms for confluent flows, Probabilities of discrepancy between minima of cross-validation, Vapnik bounds and true risks, Unnamed Item, Explicit list-decodable codes with optimal rate for computationally bounded channels, An ensemble extreme learning machine for data stream classification, A constructive proof of a concentration bound for real-valued random variables, A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem, Oblivious network RAM and leveraging parallelism to achieve obliviousness, Better streaming algorithms for the maximum coverage problem, Approximability of flow shop scheduling, Makespan minimization in open shops: A polynomial time approximation scheme, Improved algorithms via approximations of probability distributions, Unnamed Item, Probabilistic quorum systems, Unnamed Item, Unnamed Item, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria