Concentration of Measure for the Analysis of Randomized Algorithms

DOI10.1017/CBO9780511581274zbMath1241.60001OpenAlexW1989274820MaRDI QIDQ5891622

Alessandro Panconesi, Devdatt P. Dubhashi

Publication date: 26 June 2012

Full work available at URL: https://doi.org/10.1017/cbo9780511581274

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20) Research exposition (monographs, survey articles) pertaining to probability theory (60-02)

Related Items (28)

On triangle estimation using tripartite independent set queries ⋮ Building quantum-one-way functions from block ciphers: Davies-Meyer and Merkle-Damgård constructions ⋮ A note on transportation cost inequalities for diffusions with reflections ⋮ Measuring the unmeasurable: an application of uncertainty quantification to Treasury bond portfolios ⋮ Monochromatic sums of squares ⋮ The complex parameter landscape of the compact genetic algorithm ⋮ A refined Hoeffding's upper tail probability bound for sum of independent random variables ⋮ An improved Hoeffding's inequality for sum of independent random variables ⋮ Classical-quantum arbitrarily varying wiretap channel: common randomness assisted code and continuity ⋮ Quantum vs. classical algorithms for solving the heat equation ⋮ The impact of heterogeneity and geometry on the proof complexity of random satisfiability ⋮ Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Talagrand's transportation inequality for SPDEs with locally monotone drifts ⋮ Unnamed Item ⋮ Functional inequalities for forward and backward diffusions ⋮ Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$ ⋮ Solving vertex cover in polynomial time on hyperbolic random graphs ⋮ Optimal Design of Process Flexibility for General Production Systems ⋮ A general estimator for the extreme value index: applications to conditional and heteroscedastic extremes ⋮ Phase transition of the 2-choices dynamics on core-periphery networks ⋮ Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes ⋮ Talagrand concentration inequalities for stochastic partial differential equations ⋮ A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols ⋮ Communities, Random Walks, and Social Sybil Defense ⋮ Quadratic transportation inequalities for SDEs with measurable drift ⋮ On a game of chance in Marc Elsberg's thriller ``GREED ⋮ Towards optimal degree distributions for left-perfect matchings in random bipartite graphs ⋮ Tight approximation bounds for maximum multi-coverage

This page was built for publication: Concentration of Measure for the Analysis of Randomized Algorithms