Probability and Computing
From MaRDI portal
Publication:5463630
DOI10.1017/CBO9780511813603zbMath1092.60001WikidataQ104609845 ScholiaQ104609845MaRDI QIDQ5463630
Michael Mitzenmacher, Eli Upfal
Publication date: 5 August 2005
Markov processes; Martingales; Random graphs; Hashing; Markov Chains; Discrete probability theory; Continuous random variables
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
60-08: Computational methods for problems pertaining to probability theory
60-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to probability theory
60C05: Combinatorial probability
68W20: Randomized algorithms
Related Items
On Mixing and Edge Expansion Properties in Randomized Broadcasting, Sensor Network Gossiping or How to Break the Broadcast Lower Bound, Efficient Fully-Simulatable Oblivious Transfer, On Euclidean norm approximations, More on the Magnus-Derek game, On the runtime and robustness of randomized broadcasting, Complexity issues in color-preserving graph embeddings, A universal online caching algorithm based on pattern matching, Stability in the self-organized evolution of networks, On mixing and edge expansion properties in randomized broadcasting, Robust gossiping with an application to consensus, Randomized algorithm for the sum selection problem, Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning, Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers, Improved random graph isomorphism, Nanowire addressing with randomized-contact decoders, A self-stabilizing algorithm for cut problems in synchronous networks, On the probability of a rational outcome for generalized social welfare functions on three alternatives, An approximation trichotomy for Boolean \#CSP, The power of choice in growing trees, Choice-memory tradeoff in allocations, A robust randomized algorithm to perform independent tasks, On randomized broadcasting in star graphs, Markov type inequalities for fuzzy integrals, Matrix norms and rapid mixing for spin systems, Broadcasting in dynamic radio networks, Energy efficient randomised communication in unknown AdHoc networks, Spreading messages, The impact of parametrization in memetic evolutionary algorithms, Scale free interval graphs, Using theorem proving to verify expectation and variance for discrete random variables, The Gibbs cloner for combinatorial optimization, counting and sampling, Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work, Efficient importance sampling for binary contingency tables, Probabilistic sorting and stabilization of switched systems, A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms, Path coupling without contraction, Analysis of randomized protocols for conflict-free distributed access, A dynamic programming approach to efficient sampling from Boltzmann distributions, Revisiting Randomized Parallel Load Balancing Algorithms, Loosely-Stabilizing Leader Election in Population Protocol Model, NON-BACKTRACKING RANDOM WALKS MIX FASTER, Computing Approximate Nash Equilibria in Network Congestion Games, Less hashing, same performance: Building a better Bloom filter, Expected coalescence time for a nonuniform allocation process, Shape Matching by Random Sampling, Formal verification of tail distribution bounds in the HOL theorem prover
