Probability and Computing

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

zbMATH Keywords

Markov processesMartingalesRandom graphsHashingMarkov ChainsDiscrete probability theoryContinuous 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 (only showing first 100 items - show all)

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 ⋮ Rank of random half-integral polytopes — extended abstract —

This page was built for publication: Probability and Computing