Derandomizing complexity classes

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 -