Derandomizing complexity classes

Peter Bro Miltersen; Sanguthevar Rajasekaran; Panos Miltiades Pardalos; John Henry Reif; José Diaulas Palazzo Rolim

Derandomizing complexity classes

Peter Bro Miltersen, Sanguthevar Rajasekaran (Editor), Panos Miltiades Pardalos (Editor), John Henry Reif (Editor), José Diaulas Palazzo Rolim (Editor)

Research output: Contribution to book/anthology/report/proceeding › Book chapter › Research

Abstract

Consider a randomized algorithm, such as the Rabin primality test of Rabin, 1976. This algorithm is given as input an integer n, and as auxiliary input, a sequence of coin tosses, i.e., a vector of unbiased independent random bits. The test gives as output either "n is a prime" or "n is not a prime". For every input n, the probability that the output is a false statement is bounded form above by a small constant say ¼.

The test runs in time polynomial in the size of the binary representation of n. In particular, the number r of random bits needed is polynomial in log n.

Original language	English
Title of host publication	Handbook on Randomized Computing : Combinatorial Optimization, Vol. 9
Number of pages	92
Volume	II, chapter 19
Publisher	Kluwer Academic Publishers (Springer)
Publication date	2001
Edition	chapter 19
Pages	843-935
ISBN (Print)	978-0-7923-6959-9
ISBN (Electronic)	0-7923-6957-9
Publication status	Published - 2001

Cite this

@inbook{abe7eba09da511dcbee902004c4f4f50,

title = "Derandomizing complexity classes",

abstract = "Consider a randomized algorithm, such as the Rabin primality test of Rabin, 1976. This algorithm is given as input an integer n, and as auxiliary input, a sequence of coin tosses, i.e., a vector of unbiased independent random bits. The test gives as output either {"}n is a prime{"} or {"}n is not a prime{"}. For every input n, the probability that the output is a false statement is bounded form above by a small constant say ¼. The test runs in time polynomial in the size of the binary representation of n. In particular, the number r of random bits needed is polynomial in log n.",

author = "Miltersen, {Peter Bro} and Sanguthevar Rajasekaran and Pardalos, {Panos Miltiades} and Reif, {John Henry} and Rolim, {Jos{\'e} Diaulas Palazzo}",

year = "2001",

language = "English",

isbn = "978-0-7923-6959-9",

volume = "II, chapter 19",

pages = "843--935",

booktitle = "Handbook on Randomized Computing",

publisher = "Kluwer Academic Publishers (Springer)",

edition = "chapter 19",

}

Derandomizing complexity classes. / Miltersen, Peter Bro; Rajasekaran, Sanguthevar (Editor); Pardalos, Panos Miltiades (Editor) et al.
Handbook on Randomized Computing: Combinatorial Optimization, Vol. 9. Vol. II, chapter 19 chapter 19. ed. Kluwer Academic Publishers (Springer), 2001. p. 843-935.

Research output: Contribution to book/anthology/report/proceeding › Book chapter › Research

TY - CHAP

T1 - Derandomizing complexity classes

AU - Miltersen, Peter Bro

A2 - Rajasekaran, Sanguthevar

A2 - Pardalos, Panos Miltiades

A2 - Reif, John Henry

A2 - Rolim, José Diaulas Palazzo

PY - 2001

Y1 - 2001

N2 - Consider a randomized algorithm, such as the Rabin primality test of Rabin, 1976. This algorithm is given as input an integer n, and as auxiliary input, a sequence of coin tosses, i.e., a vector of unbiased independent random bits. The test gives as output either "n is a prime" or "n is not a prime". For every input n, the probability that the output is a false statement is bounded form above by a small constant say ¼. The test runs in time polynomial in the size of the binary representation of n. In particular, the number r of random bits needed is polynomial in log n.

AB - Consider a randomized algorithm, such as the Rabin primality test of Rabin, 1976. This algorithm is given as input an integer n, and as auxiliary input, a sequence of coin tosses, i.e., a vector of unbiased independent random bits. The test gives as output either "n is a prime" or "n is not a prime". For every input n, the probability that the output is a false statement is bounded form above by a small constant say ¼. The test runs in time polynomial in the size of the binary representation of n. In particular, the number r of random bits needed is polynomial in log n.

M3 - Book chapter

SN - 978-0-7923-6959-9

VL - II, chapter 19

SP - 843

EP - 935

BT - Handbook on Randomized Computing

PB - Kluwer Academic Publishers (Springer)

ER -

Derandomizing complexity classes

Abstract

Fingerprint

Cite this