A guided tour of Chernoff bounds
From MaRDI portal
Publication:915256
DOI10.1016/0020-0190(90)90214-IzbMath0702.60021OpenAlexW2057399436WikidataQ56430039 ScholiaQ56430039MaRDI QIDQ915256
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(90)90214-i
Related Items
Coloring bipartite graphs with semi-small list size, Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE, On binomial quantile and proportion bounds: With applications in engineering and informatics, Simplified Chernoff bounds with powers-of-two probabilities, Streaming submodular maximization with the chance constraint, Zip-zip trees: making zip trees more balanced, biased, compact, or persistent, Fast separator decomposition for finite element meshes, Probabilistic analysis of local search and NP-completeness result for constraint satisfaction, Sequential testing for elicitable functionals via supermartingales, Dynamic dictionaries for multisets and counting filters with constant time operations, Efficient web searching using temporal factors, Spanning surfaces in \(3\)-graphs, On counting point-hyperplane incidences, A provably fast linear-expected-time maxima-finding algorithm, Finding a target subnetwork in sparse networks with random faults, On learning monotone DNF under product distributions, Concurrent imitation dynamics in congestion games, Flit-serial packet routing on meshes and tori, Blinking model and synchronization in small-world networks with a time-varying coupling, On the runtime and robustness of randomized broadcasting, Randomized metarounding, Balanced allocation and dictionaries with tightly packed constant size bins, Estimating the interaction graph of stochastic neuronal dynamics by observing only pairs of neurons, Fast message dissemination in random geometric networks, Hard graphs for randomized subgraph exclusion algorithms, Safe and efficient traffic laws for mobile robots, Efficient parallel computing with memory faults, Optimal multi-packet routing on the torus, Dynamic closest pairs — A probabilistic approach, Large alphabets and incompressibility, Analysis of evolutionary algorithms for the longest common subsequence problem, Fast diagnosis of multiprocessor systems with random faults, Learning a subclass of regular patterns in polynomial time, Exploiting storage redundancy to speed up randomized shared memory simulations, Exploiting few inversions when sorting: Sequential and parallel algorithms, A cell-based population control of Monte Carlo particles for the global variance reduction for transport equations, Approximating Wardrop equilibria with finitely many agents, Unnamed Item, Agent-based randomized broadcasting in large networks, Feasibility and complexity of broadcasting with random transmission failures, Games with Symmetric Incomplete Information and Asymmetric Computational Resources, Upper and lower bounds for some depth-3 circuit classes, Resolving Braess's paradox in random networks, Randomized search trees, On the structure and complexity of worst-case equilibria, A probably fast, provably optimal algorithm for rectilinear Steiner trees, Randomised broadcasting: memory vs. randomness, Fast and optimal simulations between CRCW PRAMs, The log-star revolution, Optimal bounds for the approximation of Boolean functions and some applications, Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model, Analysis and application of adaptive sampling, Faster deterministic sorting through better sampling., Local event boundary detection with unreliable sensors: analysis of the majority vote scheme, Token transfer in a faulty network, Analysis of local search landscapes for \(k\)-SAT instances, SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS, Covering lattice points by subspaces and counting point-hyperplane incidences, Feasible reductions to Kolmogorov-Loveland stochastic sequences, Kahane-Khinchin type averages, Sparse networks tolerating random faults., Book review of: D. P. Dubhashi and A. Panconesi, Concentration of measure for the analysis of randomized algorithms., The cook-book approach to the differential equation method, Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems, Store-and-forward multicast routing on the mesh, On Radio Broadcasting in Random Geometric Graphs, Crumbling walls: a class of practical and efficient quorum systems, Sparse networks supporting efficient reliable broadcasting, Thinning protocols for routing \(h\)-relations over shared media, Broadcasting in complete networks with faulty nodes using unreliable calls, Bounded size bias coupling: a gamma function bound, and universal Dickman-function behavior, Reliable computations on faulty EREW PRAM, A simple randomized parallel algorithm for maximal f-matchings, Randomized multipacket routing and sorting on meshes, Fast randomized parallel methods for planar convex hull construction, Randomized allocation processes, On the greedy algorithm for satisfiability, Improved behaviour of tries by adaptive branching, An Upper Bound on the Space Complexity of Random Formulae in Resolution, Optimal encoding of non-stationary sources, Radio communication in random graphs, Reliable Broadcasting in Hypercubes with Random Link and Node Failures, Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes, The diameter and connectivity of networks with random dependent faults, Efficient Broadcasting in Random Power Law Networks, Power-law partial correlation network models, Posterior contraction in sparse Bayesian factor models for massive covariance matrices, Improved inequalities for the Poisson and binomial distribution and upper tail quantile functions, Cautious active clustering, Randomized interpolation and approximation of sparse polynomials stPreliminary version, A tail estimate for Mulmuley's segment intersection algorithm, Randomized strategies for the plurality problem, On randomized broadcasting in star graphs, A practical approximation algorithm for the LMS line estimator, On the computational power of depth-2 circuits with threshold and modulo gates, Sorting in linear time?, Percolation of new products, PKDPA: An Enhanced Probabilistic Differential Power Attack Methodology, Detecting a botnet in a network, Optimal many-to-one routing on the mesh with constant queues, FAST BROADCASTING WITH BYZANTINE FAULTS, Ramsey functions involving \(K_{m,n}\) with \(n\) large, Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion, Combining fuzzy information from multiple systems, Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions., On the decisional complexity of problems over the reals, Distributed probabilistic polling and applications to proportionate agreement, Locally consistent constraint satisfaction problems, Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time, Sequential Sampling for Optimal Weighted Least Squares Approximations in Hierarchical Spaces, Communication complexity of quasirandom rumor spreading
Cites Work
