Probability and Computing

DOI10.1017/CBO9780511813603zbMath1092.60001OpenAlexW2899702797WikidataQ104609845 ScholiaQ104609845MaRDI QIDQ5463630

Publication date: 5 August 2005

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

Markov processes Martingales Random graphs Hashing Markov Chains Discrete probability theory Continuous random variables

Mathematics Subject Classification ID

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

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, Communication with contextual uncertainty, Populations can be essential in tracking dynamic optima, The rectangle covering number of random Boolean matrices, Oblivious key-value stores and amplification for private set intersection, A fast network-decomposition algorithm and its applications to constant-time distributed computation, Randomized OBDD-based graph algorithms, On fast and robust information spreading in the vertex-congest model, Mixed preferential attachment model: homophily and minorities in social networks, Maximum throughput of multiple access channels in adversarial environments, On the gold standard for security of universal steganography, Efficient importance sampling for binary contingency tables, Vehicle routing with probabilistic capacity constraints, Probabilistic sorting and stabilization of switched systems, Models of random knots, Secure multi-party computation in large networks, Fault-tolerant aggregation: flow-updating meets mass-distribution, Improved analysis of the online set cover problem with advice, Strong-majority bootstrap percolation on regular graphs with low dissemination threshold, Multiple (truncated) differential cryptanalysis: explicit upper bounds on data complexity, SPEck: mining statistically-significant sequential patterns efficiently with exact sampling, Efficient pattern matching on big uncertain graphs, Rigorous upper bounds on data complexities of block cipher cryptanalysis, Central limit theorems for patterns in multiset permutations and set partitions, Spectral and structural properties of random interdependent networks, Kleinberg's grid unchained, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, A lower bound on the average degree forcing a minor, Mixing length scales of low temperature spin plaquettes models, The advice complexity of a class of hard online problems, On the expansion and diameter of bluetooth-like topologies, Top-$k$ frequent items and item frequency tracking over sliding windows of any size, Smoothed analysis of partitioning algorithms for Euclidean functionals, On the coupling time of the heat-bath process for the Fortuin-Kasteleyn random-cluster model, 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, 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, Netter: probabilistic, stateful network models, Fast approximation of betweenness centrality through sampling, Multiplicative up-drift, Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes, High-dimensional approximate $r$-nets, A time optimized scheme for top-$ k$ list maintenance over incomplete data streams, The choice of the offspring population size in the $(1,\lambda)$ evolutionary algorithm, Performance analysis of randomised search heuristics operating with a fixed budget, On the convergence of bivariate order statistics: almost sure convergence and convergence rate, Pricing lotteries, Asymptotic properties of combinatorial optimization problems in $p$-adic space, Improving MinHash via the containment index with applications to metagenomic analysis, Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work, Redundancy in distributed proofs, A fully polynomial-time approximation scheme for approximating a sum of random variables, 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, Anderson polymer in a fractional Brownian environment: asymptotic behavior of the partition function, Analysis of the single-permutation encrypted Davies-Meyer construction, The effect of handicaps on turnout for large electorates with an application to assessment voting, 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, Fair resource allocation for demands with sharp lower tail inequalities, A selectable sloppy heap, The power of thinning in balanced allocation, Self-orthogonal quasi-abelian codes are asymptotically good, The impact of parametrization in memetic evolutionary algorithms, Information dissemination in wireless ad-hoc networks under the weighted-TIM framework, Beyond conventional security in sponge-based authenticated encryption modes, Noisy rumor spreading and plurality consensus, Information geometry approach to parameter estimation in hidden Markov model, Scale free interval graphs, Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem, Breaking the $\log n$ barrier on rumor spreading, Using theorem proving to verify expectation and variance for discrete random variables, Singletons for simpletons revisiting windowed backoff with Chernoff bounds, The Gibbs cloner for combinatorial optimization, counting and sampling, Eigenvector-based identification of bipartite subgraphs, Triangle packing and covering in dense random graphs, A new lower bound on the maximum number of plane graphs using production matrices, Linking and cutting spanning trees, Approximate counting of standard set-valued tableaux, Non-standard analysis in dynamic geometry, Towards convergence rate analysis of random forests for classification, Minimum distance estimation of the binormal ROC curve, Lower bounds for boxicity, Linear controller design for chance constrained systems, From one to many rainbow Hamiltonian cycles, 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, Limitations of sums of bounded read formulas and ABPs, Balanced Allocation: Patience Is Not a Virtue, Monte Carlo Methods for Estimating the Diagonal of a Real Symmetric Matrix, Lipschitz bijections between boolean functions, Random $ \Theta (\log n) $ -CNFs are Hard for Cutting Planes, Fast Distributed Approximation for Max-Cut, Unnamed Item, Uniform estimates for almost primes over finite fields, Routing and scheduling for energy and delay minimization in the powerdown model, A Service System with Packing Constraints: Greedy Randomized Algorithm Achieving Sublinear in Scale Optimality Gap, A Short List of Equalities Induces Large Sign-Rank, Leader Election Requires Logarithmic Time in Population Protocols, Counting Solutions to Random CNF Formulas, The smoothed number of Pareto-optimal solutions in bicriteria integer optimization, The expected loss of feature diversity (versus phylogenetic diversity) following rapid extinction at the present, Stochastic Rounding Variance and Probabilistic Bounds: A New Approach, Skew-polynomial-sparse matrix multiplication, Complete characterization of broadcast and pseudo-signatures from correlations, Unnamed Item, Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, POISSON HYPERPLANE PROCESSES AND APPROXIMATION OF CONVEX BODIES, Mean Field Equilibria for Resource Competition in Spatial Settings, Unnamed Item, Randomized Rumour Spreading: The Effect of the Network Topology, Unnamed Item, Simple and Efficient Leader Election, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, Sylvester-Gallai type theorems for quadratic polynomials, Order optimal information spreading using algebraic gossip, On Mixing and Edge Expansion Properties in Randomized Broadcasting, Sensor Network Gossiping or How to Break the Broadcast Lower Bound, Diffusion in Random Networks: Impact of Degree Distribution, Eigenvector Computation and Community Detection in Asynchronous Gossip Models, On Computing the Total Variation Distance of Hidden Markov Models., Probabilistic Error Analysis for Inner Products, Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non‐adaptiveness, Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations, Unnamed Item, Unnamed Item, Characterizing optimal sampling of binary contingency tables via the configuration model, TAIL PROBABILITIES IN QUEUEING PROCESSES, Total Vertex Irregularity Strength of Dense Graphs, The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata, Balls into bins via local search: Cover time and maximum load, Quick Detection of Nodes with Large Degrees, Unnamed Item, Parameterized Traveling Salesman Problem: Beating the Average, Distributed construction of purely additive spanners, Unnamed Item, Unnamed Item, Fast distributed algorithms for testing graph properties, Coping with Silent Errors in HPC Applications, Topology-hiding computation on all graphs, Subquadratic non-adaptive threshold group testing, Efficient $k$-shot broadcasting in radio networks, An exponential limit shape of random $q$-proportion Bulgarian solitaire, Bounding the scaling window of random constraint satisfaction problems, Probabilistic learnability of context-free grammars with basic distributional properties from positive examples, Separation dimension and degree, Efficient Fully-Simulatable Oblivious Transfer, $\ell_1$-sparsity approximation bounds for packing integer programs, Optimality of Correlated Sampling Strategies, Optimal channel utilization with limited feedback, Finding a mediocre player, Randomized generation of error control codes with automata and transducers, Approximate Neighbor Counting in Radio Networks, Stochastic Online Metric Matching, Approximate Counting of k-Paths: Deterministic and in Polynomial Space, Selection Algorithms with Small Groups, Verifiable Stream Computation and Arthur--Merlin Communication, Communities, Random Walks, and Social Sybil Defense, Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank, Concentration and Moment Inequalities for Polynomials of Independent Random Variables, Exact Camera Location Recovery by Least Unsquared Deviations, Robust randomized optimization with k nearest neighbors, Nearly Perfect Matchings in Uniform Hypergraphs, ON DISCRETE STOCHASTIC PROCESSES WITH DISJUNCTIVE OUTCOMES, On the Complexity of Universal Leader Election, Strong Algorithms for the Ordinal Matroid Secretary Problem, Discrete-time classical and quantum Markovian evolutions: Maximum entropy problems on path space, A lower bound on the ground state energy of dilute Bose gas, Multi-partite squash operation and its application to device-independent quantum key distribution, Sequential stratified splitting for efficient Monte Carlo integration, Coordination problems on networks revisited: statics and dynamics, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model, Reed-Muller Codes, Sorting with Recurrent Comparison Errors, Efficiently approximating the probability of deadline misses in real-time systems, Strong dispersion property for the quantum walk on the hypercube, Mechanism Design for Correlated Valuations: Efficient Methods for Revenue Maximization, Efficient live exploration of a dynamic ring with mobile robots, The coverage ratio of the frog model on complete graphs, Multiple random walks on graphs: mixing few to cover many, Improved methods to compare distance metrics in networks using uniform random spanning trees (DIMECOST), Precision-aware deterministic and probabilistic error bounds for floating point summation, Multi-twisted additive codes over finite fields are asymptotically good, ROhAN: row-order agnostic null models for statistically-sound knowledge discovery, Runtime Analysis of a Co-Evolutionary Algorithm, Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers, The directed spanning forest in the hyperbolic space, Long-term balanced allocation via thinning, Fair Influence Maximization in Large-scale Social Networks Based on Attribute-aware Reverse Influence Sampling, Hamilton cycles in dense regular digraphs and oriented graphs, Asymptotically good $\mathbb{Z}_p\mathbb{Z}_p[u/\langle u^t\rangle$-additive cyclic codes], Foundations for entailment checking in quantitative separation logic, Poly onions: achieving anonymity in the presence of churn, Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax, Multi-twisted additive self-orthogonal and ACD codes are asymptotically good, Lower bounds for the Turán densities of daisies, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Rank of random half-integral polytopes — extended abstract —, On the Diameter of Hyperbolic Random Graphs, Serving in the Dark should be done Non-Uniformly, The Complexity of Problems in P Given Correlated Instances, On Conflict-Free Multi-coloring, Select with Groups of 3 or 4, DEX: self-healing expanders, Satisfiability Thresholds beyond k −XORSAT, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Computing approximate Nash equilibria in network congestion games, QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find, On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem, Random Sampling of Trivial Words in Finitely Presented Groups, Bounds for algebraic gossip on graphs, Submodular Functions: Learnability, Structure, and Optimization, Identifying structural hole spanners to maximally block information propagation, Efficient random graph matching via degree profiles, Uniform random posets, Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial, Probabilistic analysis of optimization problems on generalized random shortest path metrics, Polynomial time approximation schemes for all 1-center problems on metric rational set similarities, Computing the largest bond and the maximum connected cut of a graph, Who are you? Secure identities in single hop ad hoc networks, Online packet-routing in grids with bounded buffers, The complexity of optimal design of temporally connected graphs, Randomized matrix-free trace and log-determinant estimators, Inverse Sampling for Nonasymptotic Sequential Estimation of Bounded Variable Means, On the analysis of Bloom filters, Reinforcement learning for combinatorial optimization: a survey, On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism, Smoothed Analysis on Connected Graphs, Push is Fast on Sparse Random Graphs, NON-BACKTRACKING RANDOM WALKS MIX FASTER, Approximately Counting Triangles in Sublinear Time, The loss of serving in the dark, Household-Level Economies of Scale in Transportation, On state estimation for nonlinear systems under random access wireless protocols, Optimizing static and adaptive probing schedules for rapid event detection, Computing Approximate Nash Equilibria in Network Congestion Games, A complexity classification of spin systems with an external field, On smoothed analysis of quicksort and Hoare's find, Concentration of rainbow $k$-connectivity of a multiplex random graph, On zero-sum free sequences contained in random subsets of finite cyclic groups, Improving the Randomization Step in Feasibility Pump, Probability distributions for Markov chain based quantum walks, Almost Perfect Matchings in $k$-Partite $k$-Graphs, An Automatic Inequality Prover and Instance Optimal Identity Testing, Random sampling in multi-window quasi shift-invariant spaces, A Power-of-Two-Choices Unbalanced Allocation Process, Leader election in well-connected graphs, Distributed Merkle's puzzles, Convex optimization for the planted $k$-disjoint-clique problem, Less hashing, same performance: Building a better Bloom filter, Random Walk in a N-Cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations, $\mathbb{F}_2[u\mathbb{F}_2[u]$-additive cyclic codes are asymptotically good], Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems, Revisiting the Security Proof of QUAD Stream Cipher: Some Corrections and Tighter Bounds, Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract), Updating Dynamic Random Hyperbolic Graphs in Sublinear Time, A simple randomized scheme for constructing low-weight $k$-connected spanning subgraphs with applications to distributed algorithms, On percolation and ‐hardness, Path coupling without contraction, Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, Regular Behavior of the Maximal Hypergraph Chromatic Number, Choice-driven phase transition in complex networks, Analysis of randomized protocols for conflict-free distributed access, Two Hardness Results on Feedback Vertex Sets, Set Covering with Ordered Replacement: Additive and Multiplicative Gaps, Rare event simulation and splitting for discontinuous random variables, Expected coalescence time for a nonuniform allocation process, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time, Shape Matching by Random Sampling, Formal verification of tail distribution bounds in the HOL theorem prover, Cubicity, degeneracy, and crossing number, On the conditional distributions and the efficient simulations of exponential integrals of Gaussian random fields, Monte Carlo and Las Vegas randomized algorithms for systems and control. An introduction, Collaborative filtering with information-rich and~information-sparse entities, Weakest Precondition Reasoning for Expected Run–Times of Probabilistic Programs, Wireless scheduling with partial channel state information: large deviations and optimality, A dynamic programming approach to efficient sampling from Boltzmann distributions, A SPIKY BALL, Discovery Through Gossip, Lower Bounds for Restricted-Use Objects, CONTENTION RESOLUTION IN MULTIPLE-ACCESS CHANNELS: k-SELECTION IN RADIO NETWORKS, Absorption time of the Moran process, Differentially Private and Budget-Limited Bandit Learning over Matroids, Bayesian Incentive-Compatible Bandit Exploration, Degree-degree distribution in a power law random intersection graph with clustering, Sub-logarithmic Test-and-Set against a Weak Adversary, Unbounded Contention Resolution in Multiple-Access Channels, Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers, A Well-Tempered Landscape for Non-convex Robust Subspace Recovery, Sparsifying Congested Cliques and Core-Periphery Networks, Revisiting Randomized Parallel Load Balancing Algorithms, Loosely-Stabilizing Leader Election in Population Protocol Model, On the Use of Smoothing to Improve the Performance of the Splitting Method, Local uniformity properties for glauber dynamics on graph colorings, A Mechanism for Communication-Efficient Broadcast Encryption over Wireless Ad Hoc Networks, Probabilistic Connectivity Threshold for Directional Antenna Widths, RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS