Chernoff–Hoeffding Bounds for Applications with Limited Independence
From MaRDI portal
Publication:4837650
DOI10.1137/S089548019223872XzbMATH Open0819.60032MaRDI QIDQ4837650FDOQ4837650
Authors: Jeanette P. Schmidt, Aravind Srinivasan, Alan Siegel 
Publication date: 3 July 1995
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Recommendations
- scientific article; zbMATH DE number 437558
- A contribution to the theory of Chernoff bounds
- An asymptotically least-favorable Chernoff bound for a large class of dependent data processes
- Tight Probability Bounds with Pairwise Independence
- Chernoff-type inequality and variance bounds
- An Identity of Chernoff Bounds With an Interpretation in Statistical Physics and Applications in Information Theory
- Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
- A generalization of Chernoff inequality via stochastic analysis
large deviationsrandomized algorithmsderandomizationChernoff-Hoeffding boundscorrelation inequalitiesdeterministic simulationlimited independence
Multivariate distribution of statistics (62H10) Large deviations (60F10) Inequalities; stochastic orderings (60E15) Sums of independent random variables; random walks (60G50) Discrete mathematics in relation to computer science (68R99) Combinatorial probability (60C05) Factorials, binomial coefficients, combinatorial functions (05A10) Theory of computing (68Q99)
Cited In (56)
- Leveraging parameterized Chernoff bounds for simplified algorithm analyses
- Distributed Symmetry Breaking on Power Graphs via Sparsification
- A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints
- On almost-uniform generation of SAT solutions: the power of 3-wise independent hashing
- Distributed constructions of dual-failure fault-tolerant distance preservers
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Oblivious network RAM and leveraging parallelism to achieve obliviousness
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- The number of rational points of hyperelliptic curves over subsets of finite fields
- Probabilities of discrepancy between minima of cross-validation, Vapnik bounds and true risks
- Dynamic dictionaries for multisets and counting filters with constant time operations
- Improved algorithms via approximations of probability distributions
- Sketching asynchronous data streams over sliding windows
- Title not available (Why is that?)
- An asymptotically least-favorable Chernoff bound for a large class of dependent data processes
- A Framework for Adversarially Robust Streaming Algorithms
- A note on the distribution of the number of prime factors of the integers
- Derandomizing local distributed algorithms under bandwidth restrictions
- How good is a dense shop schedule?
- Competitive throughput in multi-hop wireless networks despite adaptive jamming
- Algorithms and lower bounds for comparator circuits from shrinkage
- Nearly-perfect hypergraph packing is in NC
- Better streaming algorithms for the maximum coverage problem
- On the approximability of clique and related maximization problems
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
- On the Bernstein-Hoeffding method
- Tight Probability Bounds with Pairwise Independence
- Probabilistic quorum systems
- Approximation algorithms for multiprocessor scheduling under uncertainty
- Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms
- Title not available (Why is that?)
- Cache-oblivious hashing
- Collaborate with strangers to find own preferences
- Optimal hashing in external memory
- Maximizing Throughput in Flow Shop Real-Time Scheduling
- A study on several combination problems of classic shop scheduling and shortest path
- Makespan minimization in open shops: A polynomial time approximation scheme
- Dynamic dictionaries for multisets and counting filters with constant time operations
- An ensemble extreme learning machine for data stream classification
- Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
- Quicksort, largest bucket, and min-wise hashing with limited independence
- Using hashing to solve the dictionary problem
- Detecting communities is hard (and counting them is even harder)
- Approximability of flow shop scheduling
- Hoeffding's inequality for sums of dependent random variables
- Cost-sharing mechanisms for network design
- Fooling Polytopes
- Singletons for simpletons revisiting windowed backoff with Chernoff bounds
- Pseudorandomness via the discrete Fourier transform
- A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
- A constructive proof of a concentration bound for real-valued random variables
- Meet and merge: approximation algorithms for confluent flows
- Time-message trade-offs in distributed algorithms
- Improved parallel approximation of a class of integer programming problems
- Hölder-type inequalities and their applications to concentration and correlation bounds
This page was built for publication: Chernoff–Hoeffding Bounds for Applications with Limited Independence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4837650)
