Introducing Quasirandomness to Computer Science

DOI10.1007/978-3-642-03456-5_6zbMath1258.68100MaRDI QIDQ3644716

Benjamin Doerr

Publication date: 12 November 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03456-5_6

Mathematics Subject Classification ID

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Deterministic Random Walks for Rapidly Mixing Chains, Deterministic random walks on finite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The shortest-path problem for graphs with random arc-lengths
• Tight bounds for quasirandom rumor spreading
• Randomized broadcast in networks
• A Remark on Stirling's Formula
• Graph Theory and Probability
• Undirected ST-connectivity in log-space
• Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• The inverse of the star-discrepancy depends linearly on the dimension
• On Mixing and Edge Expansion Properties in Randomized Broadcasting
• Quasirandom rumor spreading
• On the Runtime and Robustness of Randomized Broadcasting
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
• Geometric discrepancy. An illustrated guide