Probability and Computing
From MaRDI portal
Publication:5463630
DOI10.1017/CBO9780511813603zbMath1092.60001OpenAlexW2899702797WikidataQ104609845 ScholiaQ104609845MaRDI QIDQ5463630
Eli Upfal, Michael Mitzenmacher
Publication date: 5 August 2005
Full work available at URL: https://doi.org/10.1017/cbo9780511813603
Markov processesMartingalesRandom graphsHashingMarkov ChainsDiscrete probability theoryContinuous random variables
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Computational methods for problems pertaining to probability theory (60-08) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to probability theory (60-01) Combinatorial probability (60C05) Randomized algorithms (68W20)
Related Items (only showing first 100 items - show all)
Asymptotic existence of proportionally fair allocations ⋮ Cryptanalysis of a dynamic universal accumulator over bilinear groups ⋮ A survey of the modified Moran process and evolutionary graph theory ⋮ Measuring the impact of adversarial errors on packet scheduling strategies ⋮ The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ Simple and optimal randomized fault-tolerant rumor spreading ⋮ Secret-sharing schemes for very dense graphs ⋮ On the runtime and robustness of randomized broadcasting ⋮ Runtime analysis of non-elitist populations: from classical optimisation to partial information ⋮ The impact of random initialization on the runtime of randomized search heuristics ⋮ Information geometry approach to parameter estimation in Markov chains ⋮ A unified framework for linear dimensionality reduction in L1 ⋮ 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 ⋮ The union-closed sets conjecture almost holds for almost all random bipartite graphs ⋮ Succinct posets ⋮ Robust gossiping with an application to consensus ⋮ Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems ⋮ Random convolution of inhomogeneous distributions with \(\mathcal {O} \)-exponential tail ⋮ Approximation of smallest linear tree grammar ⋮ \((\alpha,\tau )\)-monitoring for event detection in wireless sensor networks ⋮ Time efficient \(k\)-shot broadcasting in known topology radio networks ⋮ Stochastic enumeration method for counting NP-hard problems ⋮ Efficient and robust associative memory from a generalized Bloom filter ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ External-memory multimaps ⋮ Unbounded contention resolution in multiple-access channels ⋮ A random sampling approach to worst-case design of structures ⋮ Randomized algorithm for the sum selection problem ⋮ On Euclidean norm approximations ⋮ Logit dynamics with concurrent updates for local interaction potential games ⋮ More on the Magnus-Derek game ⋮ Design and analysis of migration in parallel evolutionary algorithms ⋮ The limits of tractability in resolution-based propositional proof systems ⋮ Running time analysis of ant colony optimization for shortest path problems ⋮ Going around in circles ⋮ The use of tail inequalities on the probable computational time of randomized search heuristics ⋮ Hybridizing evolutionary algorithms with variable-depth search to overcome local optima ⋮ Random half-integral polytopes ⋮ Pattern hit-and-run for sampling efficiently on polytopes ⋮ Efficient Monte Carlo for high excursions of Gaussian random fields ⋮ Shape matching by random sampling ⋮ Revisiting randomized parallel load balancing algorithms ⋮ Loosely-stabilizing leader election in a population protocol model ⋮ Limiting size index distributions for ball-bin models with Zipf-type frequencies ⋮ 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 ⋮ The number of \(K_{m,m}\)-free graphs ⋮ Derandomization in game-theoretic probability ⋮ Rigorous error control methods for estimating means of bounded random variables ⋮ Secure and highly-available aggregation queries in large-scale sensor networks via set sampling ⋮ Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning ⋮ Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons ⋮ Minimum clique partition in unit disk graphs ⋮ Competitive analysis of maintaining frequent items of a stream ⋮ Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances ⋮ Fast distributed PageRank computation ⋮ The mean-field computation in a supermarket model with server multiple vacations ⋮ Identifying frequent items in a network using gossip ⋮ Randomized methods based on new Monte Carlo schemes for control and optimization ⋮ The dropout learning algorithm ⋮ Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers ⋮ Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem ⋮ Approximation of grammar-based compression via recompression ⋮ Block-structured supermarket models ⋮ Improved and simplified inapproximability for \(k\)-means ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ Improved random graph isomorphism ⋮ Nanowire addressing with randomized-contact decoders ⋮ Doing-it-all with bounded work and communication ⋮ A self-stabilizing algorithm for cut problems in synchronous networks ⋮ Efficient decentralized algorithms for the distributed trigger counting problem ⋮ On the number of binary-minded individuals required to compute \(\sqrt {\frac 12}\) ⋮ On the probability of a rational outcome for generalized social welfare functions on three alternatives ⋮ Exact computation of minimum sample size for estimation of binomial parameters ⋮ On success runs of length exceeded a threshold ⋮ Sorting and selection on dynamic data ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ An approximation trichotomy for Boolean \#CSP ⋮ The power of choice in growing trees ⋮ A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model ⋮ Monitoring churn in wireless networks ⋮ Energy efficient alert in single-hop networks of extremely weak devices ⋮ Nuclear norm minimization for the planted clique and biclique problems ⋮ Secure and self-stabilizing clock synchronization in sensor networks ⋮ Choice-memory tradeoff in allocations ⋮ A communication-efficient private matching scheme in client-server model ⋮ 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 ⋮ The complexity of approximating conservative counting CSPs ⋮ Broadcasting in dynamic radio networks ⋮ Decoupling with random quantum circuits ⋮ Energy efficient randomised communication in unknown AdHoc networks ⋮ Spreading messages ⋮ A symmetric cryptographic scheme for data integrity verification in cloud databases ⋮ Most binary matrices have no small defining set
This page was built for publication: Probability and Computing
