Concentration of Measure for the Analysis of Randomized Algorithms
From MaRDI portal
Publication:5896979
DOI10.1017/CBO9780511581274zbMath1213.60006OpenAlexW1989274820MaRDI QIDQ5896979
Devdatt P. Dubhashi, Alessandro Panconesi
Publication date: 1 September 2009
Full work available at URL: https://doi.org/10.1017/cbo9780511581274
martingalesconcentration of measureTalagrand inequalityChernoff-Hoeffding boundsLog-Sobolev inequalities
Analysis of algorithms (68W40) Randomized algorithms (68W20) Research exposition (monographs, survey articles) pertaining to probability theory (60-02)
Related Items (only showing first 100 items - show all)
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies ⋮ Full rainbow matchings in graphs and hypergraphs ⋮ Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs ⋮ On the Diameter of Hyperbolic Random Graphs ⋮ Serving in the Dark should be done Non-Uniformly ⋮ Ultra-Fast Load Balancing on Scale-Free Networks ⋮ On the Diameter of Hyperbolic Random Graphs ⋮ Random Walks in Polytopes and Negative Dependence ⋮ List coloring triangle-free hypergraphs ⋮ Fast Output-Sensitive Matrix Multiplication ⋮ Fooling Polytopes ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ ANTS on a Plane ⋮ Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions ⋮ Asymptotic efficiency and probabilistic error bound for maximum likelihood‐based identification of finite impulse response systems with binary‐valued observations and unreliable communications ⋮ Expansion and flooding in dynamic random networks with node churn ⋮ Learning hierarchically-structured concepts ⋮ Unnamed Item ⋮ On sufficient conditions for spanning structures in dense graphs ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Semi-supervised anomaly detection in dynamic communication networks ⋮ Phase transition of the \(k\)-majority dynamics in biased communication models ⋮ Efficient computation of tight approximations to Chernoff bounds ⋮ Online max-min fair allocation ⋮ Unnamed Item ⋮ An instance-based algorithm for deciding the bias of a coin ⋮ Building blocks of sharding blockchain systems: concepts, approaches, and open problems ⋮ Unnamed Item ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Unnamed Item ⋮ On the symmetric version of Saeki's theorem and flat densities ⋮ Unnamed Item ⋮ Majority vote in social networks ⋮ Unnamed Item ⋮ Randomized Rumour Spreading: The Effect of the Network Topology ⋮ On the Method of Typical Bounded Differences ⋮ Anomaly Detection and Classification for Streaming Data using PDEs ⋮ Unnamed Item ⋮ Separation Between Deterministic and Randomized Query Complexity ⋮ Rumor spreading: A trigger for proliferation or fading away ⋮ Unnamed Item ⋮ Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems ⋮ Explosive Percolation in Erdős–Rényi-Like Random Graph Processes ⋮ Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Unnamed Item ⋮ On Comparison of Clustering Properties of Point Processes ⋮ The Number of Collisions for the Occupancy Problem with Unequal Probabilities ⋮ Equilibria of Greedy Combinatorial Auctions ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time ⋮ Coin Flipping Cannot Shorten Arithmetic Computations ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ From Monetary to Nonmonetary Mechanism Design via Artificial Currencies ⋮ On the Probabilistic Degrees of Symmetric Boolean Functions ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Unnamed Item ⋮ Mutual Inhibition with Few Inhibitory Cells via Nonlinear Inhibitory Synaptic Interaction ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ A unified approach to tail estimates for randomized incremental construction ⋮ The Communication Complexity of Distributed epsilon-Approximations ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Upper tail analysis of bucket sort and random tries ⋮ Upper tail analysis of bucket sort and random tries ⋮ Concentration and Moment Inequalities for Polynomials of Independent Random Variables ⋮ Mutation, Sexual Reproduction and Survival in Dynamic Environments ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results ⋮ Direct Search Based on Probabilistic Descent ⋮ Concentration inequalities for nonlinear matroid intersection ⋮ Tight Bounds for the Subspace Sketch Problem with Applications ⋮ Testing Probability Distributions using Conditional Samples ⋮ Low-Distortion Inference of Latent Similarities from a Multiplex Social Network ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Topics and Techniques in Distribution Testing: A Biased but Representative Sample ⋮ A lower bound for adaptively-secure collective coin flipping protocols ⋮ Transportation inequalities under uniform metric for a stochastic heat equation driven by time-white and space-colored noise ⋮ Simple and optimal randomized fault-tolerant rumor spreading ⋮ Edge-disjoint rainbow spanning trees in complete graphs ⋮ An optimal uniform concentration inequality for discrete entropies on finite alphabets in the high-dimensional setting ⋮ Runtime analysis of non-elitist populations: from classical optimisation to partial information ⋮ Concentration of first hitting times under additive drift ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Online load balancing with general reassignment cost ⋮ A tail bound for read-kfamilies of functions ⋮ Secrecy results for compound wiretap channels ⋮ Gaussian concentration and uniqueness of equilibrium states in lattice systems ⋮ Improved approximation of linear threshold functions ⋮ Kantorovich duality for general transport costs and applications ⋮ Who are you? Secure identities in single hop ad hoc networks ⋮ I/O-efficient similarity join ⋮ Parallel load balancing on constrained client-server topologies ⋮ An Improved Bound for Random Binary Search Trees with Concurrent Insertions ⋮ Upper tails for arithmetic progressions in random subsets ⋮ Partial sorting problem on evolving data ⋮ Supersaturation in posets and applications involving the container method ⋮ On the volume of unit balls of finite-dimensional Lorentz spaces ⋮ Fast error-tolerant quartet phylogeny algorithms ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
This page was built for publication: Concentration of Measure for the Analysis of Randomized Algorithms
