Probability and Computing
Continuous random variablesDiscrete probability theoryHashingMarkov ChainsMarkov processesMartingalesRandom graphs
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to probability theory (60-01) Computational methods for problems pertaining to probability theory (60-08) Combinatorial probability (60C05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40)
The book presents an introduction to the ideas and techniques used in the development of randomized algorithms and the probabilistic analysis of algorithms. Randomized algorithms make use of (pseudo) random numbers, for example to make decisions in the execution of the algorithm or as basic ingredients such as in Monte Carlo methods. Complexity theory often deals with the worst-case analysis of algorithms, in particular their performance on pathological cases. However, the latter happen quite rarely in practice. Probabilistic analysis of algorithms is concerned with studying how algorithms perform in the majority of non-pathological cases. The appropriate language to formulate concepts and results is, obviously, probability theory. The book consists of 14 chapters, the first seven of which constitute core material for a one-semester course. The second seven chapters contain more advanced material either for a second course or as additional material in a more advanced course. Chapters 1 to 3 review basic notions of probability theory, such as events and probability, discrete random variables and expectation and moments and deviations. Together with these concepts, the first examples of randomized algorithms, such as a randomized min-cut algorithm are introduced. In Chapter 4 moment generating functions and Chernoff bounds are treated. As an application a randomized technique for packet routing in sparse networks is discussed and Chernoff bounds are used to analyse the performance of the algorithm on a hypercube and on a butterfly network. Chapter 5 is concerned with balls, bins and random graphs. The probabilistic method is presented and discussed in Chapter 6, together with several variations, such as the expectation argument, the second moment method and Lovász local lemma. Chapter 7 introduces Markov chains and random walks. Models of simple queues and Parrondo's paradox are also discussed. The second part of the book begins with Chapter 8, which introduces continuous distributions and the Poisson process, as well as continuous Markov processes and Markovian queues. Chapter 9 deals with entropy, randomness, and information and Chapter 10 with the Monte Carlo method. In Chapter 11 coupling of Markov chains is treated, as examples serve the shuffling of cards and random walks on a hypercube; as an application the approximate sampling of proper colourings of a graph is presented. Chapter 12 introduces martingales and, e.g., pattern matching serves as an application of the Azuma-Hoeffding inequality. The last two chapters are devoted to pairwise independence and universal hash functions, on the one hand, and balanced allocations on the other. Each chapter has a section with exercises, most of which are theoretical, some are programming exercises. The book is very well written and contains useful material on probability theory and its application in computer science.
- Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- Randomized algorithms: Approximation, generation and counting
- Concentration of Measure for the Analysis of Randomized Algorithms
- scientific article; zbMATH DE number 819814
- 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
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Randomized OBDD-based graph algorithms
- On the gold standard for security of universal steganography
- Vehicle routing with probabilistic capacity constraints
- Models of random knots
- Multiple (truncated) differential cryptanalysis: explicit upper bounds on data complexity
- Efficient pattern matching on big uncertain graphs
- Rigorous upper bounds on data complexities of block cipher cryptanalysis
- Spectral and structural properties of random interdependent networks
- Mixing length scales of low temperature spin plaquettes models
- The advice complexity of a class of hard online problems
- On the coupling time of the heat-bath process for the Fortuin-Kasteleyn random-cluster model
- Island models meet rumor spreading
- Chebyshev polynomials, moment matching, and optimal estimation of the unseen
- Self-stabilizing repeated balls-into-bins
- Sample complexity of the distinct elements problem
- Fast approximation of betweenness centrality through sampling
- A time optimized scheme for top-\( k\) list maintenance over incomplete data streams
- On the convergence of bivariate order statistics: almost sure convergence and convergence rate
- Asymptotic properties of combinatorial optimization problems in \(p\)-adic space
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- A fully polynomial-time approximation scheme for approximating a sum of random variables
- Anderson polymer in a fractional Brownian environment: asymptotic behavior of the partition function
- Analysis of the single-permutation encrypted Davies-Meyer construction
- Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
- On the expansion and diameter of bluetooth-like topologies
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- High-dimensional approximate \(r\)-nets
- Improving MinHash via the containment index with applications to metagenomic analysis
- Redundancy in distributed proofs
- The effect of handicaps on turnout for large electorates with an application to assessment voting
- Fair resource allocation for demands with sharp lower tail inequalities
- The power of thinning in balanced allocation
- Self-orthogonal quasi-abelian codes are asymptotically good
- Information dissemination in wireless ad-hoc networks under the weighted-TIM framework
- Information geometry approach to parameter estimation in hidden Markov model
- Breaking the \(\log n\) barrier on rumor spreading
- Singletons for simpletons revisiting windowed backoff with Chernoff bounds
- Triangle packing and covering in dense random graphs
- Approximate counting of standard set-valued tableaux
- Towards convergence rate analysis of random forests for classification
- From one to many rainbow Hamiltonian cycles
- Limitations of sums of bounded read formulas and ABPs
- Oblivious key-value stores and amplification for private set intersection
- Mixed preferential attachment model: homophily and minorities in social networks
- SPEck: mining statistically-significant sequential patterns efficiently with exact sampling
- Central limit theorems for patterns in multiset permutations and set partitions
- Kleinberg's grid unchained
- A lower bound on the average degree forcing a minor
- Top-\(k\) frequent items and item frequency tracking over sliding windows of any size
- Competitive clustering of stochastic communication patterns on a ring
- Range partitioning within sublinear time: algorithms and lower bounds
- Switching competitors reduces win-stay but not lose-shift behaviour: the role of outcome-action association strength on reinforcement learning
- Disproving the normal graph conjecture
- Netter: probabilistic, stateful network models
- Multiplicative up-drift
- Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes
- The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
- Performance analysis of randomised search heuristics operating with a fixed budget
- Pricing lotteries
- Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work
- On XOR lemmas for the weight of polynomial threshold functions
- Two-stage combinatorial optimization problems under risk
- Loosely-stabilizing leader election with polylogarithmic convergence time
- Load balancing under \(d\)-thinning
- Random sampling and machine learning to understand good decompositions
- The combinatorics of hidden diversity
- Asymptotically good \(\mathbb{Z}_{p^r} \mathbb{Z}_{p^s} \)-additive cyclic codes
- Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming
- The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time
- A selectable sloppy heap
- Beyond conventional security in sponge-based authenticated encryption modes
- Noisy rumor spreading and plurality consensus
- Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
- Eigenvector-based identification of bipartite subgraphs
- A new lower bound on the maximum number of plane graphs using production matrices
- Linking and cutting spanning trees
- Non-standard analysis in dynamic geometry
- Minimum distance estimation of the binormal ROC curve
- Lower bounds for boxicity
- Linear controller design for chance constrained systems
- Probabilistic connectivity threshold for directional antenna widths
- Average case network lifetime on an interval with adjustable sensing ranges
- Excuse me! or the courteous theatregoers' problem
- Deterministic polynomial approach in the plane
- Communication complexity of quasirandom rumor spreading
- Populations can be essential in tracking dynamic optima
- The rectangle covering number of random Boolean matrices
- Maximum throughput of multiple access channels in adversarial environments
This page was built for publication: Probability and Computing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463630)