Introducing quasirandomness to computer science

Benjamin Doerr

doi:10.1007/978-3-642-03456-5_6

Introducing quasirandomness to computer science

Benjamin Doerr

Max-Planck-Institut fur Informatik

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The paradigm of quasirandomness led to dramatic progress in different areas of mathematics, with the invention of quasi-Monte Carlo methods in numerical integration probably being the best known example. In the last two decades, discrete mathematics heavily used quasirandom ideas, leading, e.g., to notions like quasirandom graphs. We feel that it is now time to exploit quasirandomness in computer science. As a first application, we propose and analyze a quasirandom analogue of the classical randomized rumor spreading protocol to disseminate information in networks.

Original language	English
Title of host publication	Efficient Algorithms
Subtitle of host publication	Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday
Editors	Susanne Albers, Helmut Alt, Stefan Naher
Pages	99-111
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-03456-5_6
Publication status	Published - 16 Oct 2009
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5760 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-642-03456-5_6

Cite this

Doerr, B. (2009). Introducing quasirandomness to computer science. In S. Albers, H. Alt, & S. Naher (Eds.), Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday (pp. 99-111). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5760 LNCS). https://doi.org/10.1007/978-3-642-03456-5_6

@inproceedings{0d73f966b4c542a2a9cbdab9e03a75ee,

title = "Introducing quasirandomness to computer science",

abstract = "The paradigm of quasirandomness led to dramatic progress in different areas of mathematics, with the invention of quasi-Monte Carlo methods in numerical integration probably being the best known example. In the last two decades, discrete mathematics heavily used quasirandom ideas, leading, e.g., to notions like quasirandom graphs. We feel that it is now time to exploit quasirandomness in computer science. As a first application, we propose and analyze a quasirandom analogue of the classical randomized rumor spreading protocol to disseminate information in networks.",

author = "Benjamin Doerr",

year = "2009",

month = oct,

day = "16",

doi = "10.1007/978-3-642-03456-5\_6",

language = "English",

isbn = "3642034551",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "99--111",

editor = "Susanne Albers and Helmut Alt and Stefan Naher",

booktitle = "Efficient Algorithms",

}

Doerr, B 2009, Introducing quasirandomness to computer science. in S Albers, H Alt & S Naher (eds), Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5760 LNCS, pp. 99-111. https://doi.org/10.1007/978-3-642-03456-5_6

Introducing quasirandomness to computer science. / Doerr, Benjamin.
Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. ed. / Susanne Albers; Helmut Alt; Stefan Naher. 2009. p. 99-111 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5760 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Introducing quasirandomness to computer science

AU - Doerr, Benjamin

PY - 2009/10/16

Y1 - 2009/10/16

N2 - The paradigm of quasirandomness led to dramatic progress in different areas of mathematics, with the invention of quasi-Monte Carlo methods in numerical integration probably being the best known example. In the last two decades, discrete mathematics heavily used quasirandom ideas, leading, e.g., to notions like quasirandom graphs. We feel that it is now time to exploit quasirandomness in computer science. As a first application, we propose and analyze a quasirandom analogue of the classical randomized rumor spreading protocol to disseminate information in networks.

AB - The paradigm of quasirandomness led to dramatic progress in different areas of mathematics, with the invention of quasi-Monte Carlo methods in numerical integration probably being the best known example. In the last two decades, discrete mathematics heavily used quasirandom ideas, leading, e.g., to notions like quasirandom graphs. We feel that it is now time to exploit quasirandomness in computer science. As a first application, we propose and analyze a quasirandom analogue of the classical randomized rumor spreading protocol to disseminate information in networks.

U2 - 10.1007/978-3-642-03456-5_6

DO - 10.1007/978-3-642-03456-5_6

M3 - Conference contribution

AN - SCOPUS:70349883936

SN - 3642034551

SN - 9783642034558

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 99

EP - 111

BT - Efficient Algorithms

A2 - Albers, Susanne

A2 - Alt, Helmut

A2 - Naher, Stefan

ER -

Doerr B. Introducing quasirandomness to computer science. In Albers S, Alt H, Naher S, editors, Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. 2009. p. 99-111. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-03456-5_6

Introducing quasirandomness to computer science

Abstract

Publication series

Access to Document

Fingerprint

Cite this